跳转至

3576. 数组元素相等转换

题目描述

给你一个大小为 n 的整数数组 nums，其中只包含 1 和 -1，以及一个整数 k。

你可以最多进行 k 次以下操作：

  • 选择一个下标 i（0 <= i < n - 1），然后将 nums[i] 和 nums[i + 1] 同时 乘以 -1。

注意：你可以在 不同 的操作中多次选择相同的下标 i。

如果在最多 k 次操作后可以使数组的所有元素相等，则返回 true；否则，返回 false。

 

示例 1：

输入： nums = [1,-1,1,-1,1], k = 3

输出： true

解释：

我们可以通过以下两次操作使数组的所有元素相等：

  • 选择下标 i = 1，将 nums[1] 和 nums[2] 同时乘以 -1。此时 nums = [1,1,-1,-1,1]。
  • 选择下标 i = 2，将 nums[2] 和 nums[3] 同时乘以 -1。此时 nums = [1,1,1,1,1]。

示例 2：

输入： nums = [-1,-1,-1,1,1,1], k = 5

输出： false

解释：

在最多 5 次操作内，无法使数组的所有元素相等。

 

提示：

  • 1 <= n == nums.length <= 105
  • nums[i] 的值为 -1 或 1。
  • 1 <= k <= n

解法

方法一：遍历计数

根据题目描述，要使得数组的所有元素相等，要么所有元素为 \(\textit{nums}[0]\)，要么所有元素为 \(-\textit{nums}[0]\)。因此，我们设计一个函数 \(\textit{check}\)，用于判断在最多 \(k\) 次操作后，数组能否变成所有元素为 \(\textit{target}\) 的形式。

该函数的思路是遍历数组，记录需要进行操作的次数。一个元素要么修改一次，要么不修改。如果当前元素与目标值相等，则不需要修改，继续遍历下一个元素；如果当前元素与目标值不相等，则需要修改，计数器加一，并将符号切换为负数，表示后续元素需要进行相反的操作。

如果遍历结束后，计数器小于等于 \(k\) 且最后一个元素的符号与目标值相同，则返回 \(\textit{true}\)，否则返回 \(\textit{false}\)。

最终答案是 \(\textit{check}(\textit{nums}[0], k)\) 或 \(\textit{check}(-\textit{nums}[0], k)\) 的结果。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组的长度。空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def canMakeEqual(self, nums: List[int], k: int) -> bool:
        def check(target: int, k: int) -> bool:
            cnt, sign = 0, 1
            for i in range(len(nums) - 1):
                x = nums[i] * sign
                if x == target:
                    sign = 1
                else:
                    sign = -1
                    cnt += 1
            return cnt <= k and nums[-1] * sign == target

        return check(nums[0], k) or check(-nums[0], k)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean canMakeEqual(int[] nums, int k) {
        return check(nums, nums[0], k) || check(nums, -nums[0], k);
    }

    private boolean check(int[] nums, int target, int k) {
        int cnt = 0, sign = 1;
        for (int i = 0; i < nums.length - 1; ++i) {
            int x = nums[i] * sign;
            if (x == target) {
                sign = 1;
            } else {
                sign = -1;
                ++cnt;
            }
        }
        return cnt <= k && nums[nums.length - 1] * sign == target;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool canMakeEqual(vector<int>& nums, int k) {
        auto check = [&](int target, int k) -> bool {
            int n = nums.size();
            int cnt = 0, sign = 1;
            for (int i = 0; i < n - 1; ++i) {
                int x = nums[i] * sign;
                if (x == target) {
                    sign = 1;
                } else {
                    sign = -1;
                    ++cnt;
                }
            }
            return cnt <= k && nums[n - 1] * sign == target;
        };
        return check(nums[0], k) || check(-nums[0], k);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func canMakeEqual(nums []int, k int) bool {
    check := func(target, k int) bool {
        cnt, sign := 0, 1
        for i := 0; i < len(nums)-1; i++ {
            x := nums[i] * sign
            if x == target {
                sign = 1
            } else {
                sign = -1
                cnt++
            }
        }
        return cnt <= k && nums[len(nums)-1]*sign == target
    }
    return check(nums[0], k) || check(-nums[0], k)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function canMakeEqual(nums: number[], k: number): boolean {
    function check(target: number, k: number): boolean {
        let [cnt, sign] = [0, 1];
        for (let i = 0; i < nums.length - 1; i++) {
            const x = nums[i] * sign;
            if (x === target) {
                sign = 1;
            } else {
                sign = -1;
                cnt++;
            }
        }
        return cnt <= k && nums[nums.length - 1] * sign === target;
    }

    return check(nums[0], k) || check(-nums[0], k);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
impl Solution {
    pub fn can_make_equal(nums: Vec<i32>, k: i32) -> bool {
        fn check(target: i32, k: i32, nums: &Vec<i32>) -> bool {
            let mut cnt = 0;
            let mut sign = 1;
            for i in 0..nums.len() - 1 {
                let x = nums[i] * sign;
                if x == target {
                    sign = 1;
                } else {
                    sign = -1;
                    cnt += 1;
                }
            }
            cnt <= k && nums[nums.len() - 1] * sign == target
        }

        check(nums[0], k, &nums) || check(-nums[0], k, &nums)
    }
}

评论