Medium

题目描述

给你一个大小为 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
解释：
我们可以通过 2 次操作使数组中的所有元素都相等：
- 选择索引 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 <= 10^5
  • nums[i] 是 -1 或 1
  • 1 <= k <= n

解题思路

这道题的关键思路是贪心算法。我们需要分别计算将所有元素转换为 1 和转换为 -1 所需的最少操作次数，然后判断是否有一种情况下操作次数不超过 k。

核心观察：

  1. 每次操作会同时改变相邻两个元素的符号
  2. 我们可以从左到右扫描数组，当遇到与目标值不同的元素时，立即进行操作
  3. 这种贪心策略是最优的，因为每次操作都能"修复"当前位置的错误

算法步骤：

  1. 定义一个辅助函数，计算将数组转换为指定目标值所需的最少操作次数
  2. 从左到右扫描数组，当当前元素与目标不符时：
    • 如果不是最后一个元素，进行操作（翻转当前和下一个元素）
    • 如果是最后一个元素且与目标不符，则无法完成转换
  3. 分别计算转换为全 1 和全 -1 的操作次数
  4. 如果任一情况的操作次数 ≤ k，则返回 true

这种方法的时间复杂度是 O(n)，空间复杂度是 O(1)。

代码实现

class Solution {
public:
    bool canMakeEqual(vector<int>& nums, int k) {
        auto minOps = [](vector<int> nums, int target) {
            int ops = 0;
            int n = nums.size();
            
            for (int i = 0; i < n; i++) {
                if (nums[i] != target) {
                    if (i == n - 1) return INT_MAX;
                    nums[i] *= -1;
                    nums[i + 1] *= -1;
                    ops++;
                }
            }
            return ops;
        };
        
        int ops1 = minOps(nums, 1);
        int ops2 = minOps(nums, -1);
        
        return ops1 <= k || ops2 <= k;
    }
};

class Solution:
    def canMakeEqual(self, nums: List[int], k: int) -> bool:
        def min_ops(arr, target):
            arr = arr[:]  # 创建副本
            ops = 0
            n = len(arr)
            
            for i in range(n):
                if arr[i] != target:
                    if i == n - 1:
                        return float('inf')
                    arr[i] *= -1
                    arr[i + 1] *= -1
                    ops += 1
            return ops
        
        ops1 = min_ops(nums, 1)
        ops2 = min_ops(nums, -1)
        
        return ops1 <= k or ops2 <= k

public class Solution {
    public bool CanMakeEqual(int[] nums, int k) {
        int MinOps(int[] arr, int target) {
            int[] temp = (int[])arr.Clone();
            int ops = 0;
            int n = temp.Length;
            
            for (int i = 0; i < n; i++) {
                if (temp[i] != target) {
                    if (i == n - 1) return int.MaxValue;
                    temp[i] *= -1;
                    temp[i + 1] *= -1;
                    ops++;
                }
            }
            return ops;
        }
        
        int ops1 = MinOps(nums, 1);
        int ops2 = MinOps(nums, -1);
        
        return ops1 <= k || ops2 <= k;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var canMakeEqual = function(nums, k) {
    const n = nums.length;
    
    // Try to make all elements equal to 1
    let operations1 = 0;
    let temp1 = [...nums];
    for (let i = 0; i < n - 1; i++) {
        if (temp1[i] === -1) {
            temp1[i] *= -1;
            temp1[i + 1] *= -1;
            operations1++;
        }
    }
    if (temp1[n - 1] === 1 && operations1 <= k) return true;
    
    // Try to make all elements equal to -1
    let operations2 = 0;
    let temp2 = [...nums];
    for (let i = 0; i < n - 1; i++) {
        if (temp2[i] === 1) {
            temp2[i] *= -1;
            temp2[i + 1] *= -1;
            operations2++;
        }
    }
    if (temp2[n - 1] === -1 && operations2 <= k) return true;
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

其中 n 是数组的长度。时间复杂度为 O(n) 因为我们需要遍历数组两次（分别计算转换为 1 和 -1 的操作次数）。空间复杂度为 O(n) 因为我们需要创建数组的副本来模拟操作过程。