Medium

题目描述

给你一个二进制数组 nums。

你可以对数组执行以下操作任意次数（可能为零）：

  • 选择数组中的任意下标 i，然后将从下标 i 到数组末尾的所有元素进行翻转。

翻转一个元素意味着将其值从 0 变为 1，或从 1 变为 0。

返回使 nums 中所有元素都等于 1 所需的最少操作次数。

示例 1：

输入：nums = [0,1,1,0,1]
输出：4
解释：
我们可以执行以下操作：
- 选择下标 i = 1，结果数组为 nums = [0,0,0,1,0]。
- 选择下标 i = 0，结果数组为 nums = [1,1,1,0,1]。
- 选择下标 i = 4，结果数组为 nums = [1,1,1,0,0]。
- 选择下标 i = 3，结果数组为 nums = [1,1,1,1,1]。

示例 2：

输入：nums = [1,0,0,0]
输出：1
解释：
我们可以执行以下操作：
- 选择下标 i = 1，结果数组为 nums = [1,1,1,1]。

提示：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 1

解题思路

解题思路

这道题的关键在于理解翻转操作的本质和最优策略。

核心观察：

  1. 每次操作会翻转从某个位置到数组末尾的所有元素
  2. 我们的目标是让所有元素都变成 1
  3. 从左到右遍历时，如果当前位置是 0，我们必须在这个位置执行翻转操作

贪心策略： 从左到右遍历数组，维护一个变量 operations 记录当前已执行的翻转操作次数。对于每个位置 i：

  • 如果 operations 是偶数，说明当前位置的值没有被改变，仍是原来的值
  • 如果 operations 是奇数，说明当前位置的值被翻转了
  • 计算当前位置的实际值：(nums[i] + operations) % 2
  • 如果实际值是 0，说明需要在这个位置执行翻转操作，operations++

正确性证明：

  • 要使 nums[0] 变成 1，唯一的方法就是在位置 0 执行翻转（如果它原本是 0）
  • 对于后续位置，如果当前值是 0，我们必须在这个位置翻转，因为这是影响这个位置的最后机会
  • 这种贪心策略保证了操作次数最少

推荐解法： 贪心算法，时间复杂度 O(n)，空间复杂度 O(1)

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int operations = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            // 计算当前位置经过翻转后的实际值
            int current = (nums[i] + operations) % 2;
            
            // 如果当前值是0，需要翻转
            if (current == 0) {
                operations++;
            }
        }
        
        return operations;
    }
};

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        operations = 0
        
        for i in range(len(nums)):
            # 计算当前位置经过翻转后的实际值
            current = (nums[i] + operations) % 2
            
            # 如果当前值是0，需要翻转
            if current == 0:
                operations += 1
        
        return operations

public class Solution {
    public int MinOperations(int[] nums) {
        int operations = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            // 计算当前位置经过翻转后的实际值
            int current = (nums[i] + operations) % 2;
            
            // 如果当前值是0，需要翻转
            if (current == 0) {
                operations++;
            }
        }
        
        return operations;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var minOperations = function(nums) {
    let operations = 0;
    let flipped = false;
    
    for (let i = 0; i < nums.length; i++) {
        let currentValue = flipped ? 1 - nums[i] : nums[i];
        
        if (currentValue === 0) {
            operations++;
            flipped = !flipped;
        }
    }
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历整个数组一次
空间复杂度O(1)只使用常数额外空间

相关题目