Transform Array to All Equal Elements

3576. 数组元素相等转换

算法

每次操作可以翻转一对相邻元素的符号
为使所有元素相等，最终需要所有元素都是 1 或 -1
从左往右遍历数组，维护一个全局的乘积影响变量 mul（表示前面的操作对当前元素造成的正负反转）
遇到第 i 个元素与目标不符时（考虑乘积影响），对 i + 1 执行一次操作（乘以 -1）
统计所需的操作次数，若超过 k 或无法继续（要翻转的下一个元素不存在），则返回 false

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

C++ 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
public:
    // 尝试将所有元素变为 target（1 或 -1）
    bool checkTransform(std::vector<int>& nums, int k, int target) {
        int mul = 1;  // 表示之前操作对当前位置的影响（1为不变，-1为取反）
        for (int i = 0; i < nums.size(); ++ i) {
            if (nums[i] * mul == target) {
                mul = 1;  // 当前符合目标，不需要额外操作
                continue;
            }
            if (k == 0 || i == nums.size() - 1) {
                return false;  // 无法再操作，失败
            }
            -- k;       // 执行一次操作
            mul = -1;  // 接下来的元素将受到影响
        }
        return true;
    }

    bool canMakeEqual(vector<int>& nums, int k) {
        // 尝试变成全为 1 或全为 -1，两种都尝试
        return checkTransform(nums, k, 1) || checkTransform(nums, k, -1);
    }
};

Python 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def checkTransform(self, nums, k, target):
        mul = 1
        for i in range(len(nums)):
            if nums[i] * mul == target:
                mul = 1
                continue
            if k == 0 or i == len(nums) - 1:
                return False
            k -= 1
            mul = -1
        return True

    def canMakeEqual(self, nums, k):
        return self.checkTransform(nums, k, 1) or self.checkTransform(nums, k, -1)

Go 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


func checkTransform(nums []int, k int, target int) bool {
    mul := 1
    for i := 0; i < len(nums); i ++ {
        if nums[i] * mul == target {
            mul = 1
            continue
        }
        if k == 0 || i == len(nums) - 1 {
            return false
        }
        k --
        mul = -1
    }
    return true
}

func canMakeEqual(nums []int, k int) bool {
    return checkTransform(nums, k, 1) || checkTransform(nums, k, -1)
}

JavaScript 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


var canMakeEqual = function (nums, k) {
  function checkTransform(nums, k, target) {
    let mul = 1;
    for (let i = 0; i < nums.length; ++i) {
      if (nums[i] * mul == target) {
        mul = 1;
        continue;
      }
      if (k == 0 || i == nums.length - 1) {
        return false;
      }
      k--;
      mul = -1;
    }
    return true;
  }

  return checkTransform(nums, k, 1) || checkTransform(nums, k, -1);
};