【2022-12-18每日一题】1703. 得到连续 K 个 1 的最少相邻交换次数[Hard]
2022-12-18
1分钟阅读时长
2022-12-18每日一题：1703. 得到连续 K 个 1 的最少相邻交换次数
难度：Hard
标签：贪心 、 数组 、 前缀和 、 滑动窗口
给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1 。每一次移动，你可以选择 相邻 两个数字并将它们交换。
请你返回使 nums 中包含 k 个 连续 1 的 最少 交换次数。
示例 1：
输入：nums = [1,0,0,1,0,1], k = 2 输出：1 解释：在第一次操作时，nums 可以变成 [1,0,0,0,1,1] 得到连续两个 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 <= 105nums[i]要么是0，要么是1。1 <= k <= sum(nums)
方法一：贪心+前缀和
func minMoves(nums []int, k int) int {
p := []int{}
for i, num := range nums {
if num == 1 {
p = append(p, i-len(p))
}
}
preSum := make([]int, len(p)+1)
for i, v := range p {
preSum[i+1] = preSum[i] + v // 计算前缀和
}
ans, m := math.MaxInt, len(p)
for i, v := range preSum[:m-k+1] {
// p[i] 到 p[i+k-1] 中所有数到 p[i+k/2] 的距离之和，取最小值
ans = min(ans, v+preSum[i+k]-preSum[i+k/2]*2-p[i+k/2]*(k%2)) // 暂未理解
}
return ans
}
func min(a, b int) int {
if b < a {
return b
}
return a
}
复杂度分析
- 时间复杂度：$O(n)$，其中 n 是数组 nums 的长度。
- 空间复杂度：$O(n)$。