Hard

题目描述

给你一个整数数组 nums 和一个整数 k。nums 仅由 0 和 1 组成。在一次移动中，你可以选择两个 相邻 的索引并交换它们的值。

返回使 nums 中包含 k 个 连续 1 所需的 最少 移动次数。

示例 1：

输入：nums = [1,0,0,1,0,1], k = 2
输出：1
解释：在 1 次移动中，nums 可以是 [1,0,0,0,1,1] 并且有 2 个连续的 1。

示例 2：

输入：nums = [1,0,0,0,0,0,1,1], k = 3
输出：5
解释：在 5 次移动中，最左边的 1 可以向右移动直到 nums = [0,0,0,0,0,1,1,1]。

示例 3：

输入：nums = [1,1,0,1], k = 2
输出：0
解释：nums 已经有 2 个连续的 1。

提示：

  • 1 <= nums.length <= 10^5
  • nums[i] 是 0 或 1
  • 1 <= k <= sum(nums)

解题思路

这道题的关键思路是：选择k个1，计算将它们移动到连续位置所需的最少交换次数。

核心观察：

  1. 要使k个1变成连续的，最优策略是将它们聚集到某个中心位置
  2. 对于k个位置的1，最优的目标位置是以某个位置为中心的连续k个位置
  3. 将1移动到目标位置的代价等于它们当前位置与目标位置的距离

算法步骤：

  1. 首先提取所有1的位置，记录在数组ones中
  2. 使用滑动窗口遍历所有可能的k个1的组合
  3. 对于每个窗口，计算将这k个1聚集到连续位置的最少移动次数
  4. 关键优化：选择中位数位置作为聚集中心，这样总移动距离最小

移动次数计算：

  • 假设选择的k个1位置为ones[i], ones[i+1], ..., ones[i+k-1]
  • 目标位置为连续的k个位置，以中位数为中心
  • 使用前缀和优化计算总移动距离

时间复杂度优化： 使用滑动窗口技术，每次移动窗口时，只需要更新边界元素的贡献，避免重复计算。

代码实现

class Solution {
public:
    int minMoves(vector<int>& nums, int k) {
        vector<int> ones;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 1) {
                ones.push_back(i);
            }
        }
        
        int n = ones.size();
        vector<long long> prefix(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + ones[i];
        }
        
        int minMoves = INT_MAX;
        for (int i = 0; i <= n - k; i++) {
            int mid = i + k / 2;
            int target = ones[mid] - k / 2;
            
            long long leftSum = prefix[mid] - prefix[i];
            long long rightSum = prefix[i + k] - prefix[mid + 1];
            
            long long leftTarget = (long long)(mid - i) * target;
            long long rightTarget = (long long)(i + k - mid - 1) * (target + k - 1);
            
            for (int j = 1; j < mid - i; j++) {
                leftTarget += target + j;
            }
            for (int j = 1; j < i + k - mid - 1; j++) {
                rightTarget += target + k - 1 - j;
            }
            
            long long moves = (leftTarget - leftSum) + (rightSum - rightTarget);
            minMoves = min(minMoves, (int)moves);
        }
        
        return minMoves;
    }
};

class Solution:
    def minMoves(self, nums: List[int], k: int) -> int:
        ones = [i for i, num in enumerate(nums) if num == 1]
        n = len(ones)
        
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + ones[i]
        
        min_moves = float('inf')
        for i in range(n - k + 1):
            mid = i + k // 2
            target = ones[mid] - k // 2
            
            left_sum = prefix[mid] - prefix[i]
            right_sum = prefix[i + k] - prefix[mid + 1]
            
            left_target = (mid - i) * target + sum(range(1, mid - i))
            right_target = (i + k - mid - 1) * (target + k - 1) + sum(range(1, i + k - mid - 1))
            
            moves = (left_target - left_sum) + (right_sum - right_target)
            min_moves = min(min_moves, moves)
        
        return min_moves

public class Solution {
    public int MinMoves(int[] nums, int k) {
        var ones = new List<int>();
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] == 1) {
                ones.Add(i);
            }
        }
        
        int n = ones.Count;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + ones[i];
        }
        
        long minMoves = long.MaxValue;
        for (int i = 0; i <= n - k; i++) {
            int mid = i + k / 2;
            int target = ones[mid] - k / 2;
            
            long leftSum = prefix[mid] - prefix[i];
            long rightSum = prefix[i + k] - prefix[mid + 1];
            
            long leftTarget = (long)(mid - i) * target;
            long rightTarget = (long)(i + k - mid - 1) * (target + k - 1);
            
            for (int j = 1; j < mid - i; j++) {
                leftTarget += target + j;
            }
            for (int j = 1; j < i + k - mid - 1; j++) {
                rightTarget += target + k - 1 - j;
            }
            
            long moves = (leftTarget - leftSum) + (rightSum - rightTarget);
            minMoves = Math.Min(minMoves, moves);
        }
        
        return (int)minMoves;
    }
}

var minMoves = function(nums, k) {
    const ones = [];
    for (let i = 0; i < nums.length; i++) {
        if (nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n + m*k)n是数组长度，m是1的个数，需要遍历所有可能的k个1的窗口
空间复杂度O(m)需要存储所有1的位置和前缀和数组

相关题目