class Solution {
public:
int minMoves(vector<int>& nums, int k) {
}
};
1703. 得到连续 K 个 1 的最少相邻交换次数
给你一个整数数组 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)原站题解
javascript 解法, 执行用时: 88 ms, 内存消耗: 63.8 MB, 提交时间: 2022-12-18 13:45:45
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var minMoves = function(nums, k) {
const g = [];
const preSum = [];
preSum.push(0);
for (let i = 0; i < nums.length; i++) {
if (nums[i] === 1) {
g.push(i - g.length);
preSum.push(preSum[preSum.length - 1] + g[g.length - 1]);
}
}
let m = g.length, res = Number.MAX_VALUE;
for (let i = 0; i <= m - k; i++) {
let mid = i + Math.floor(k / 2);
let r = g[mid];
res = Math.min(res, (1 - k % 2) * r + (preSum[i + k] - preSum[mid + 1]) - (preSum[mid] - preSum[i]));
}
return res;
};
golang 解法, 执行用时: 108 ms, 内存消耗: 7.9 MB, 提交时间: 2022-12-18 13:45:27
func minMoves(nums []int, k int) int {
n, m := len(nums), 0
for i, p := range nums {
if p != 0 {
nums[m] = i - m
m++
}
}
if m == n { // 全部都是 1
return 0
}
p := nums
var sl, sm, sr int // s[i] s[i+k/2] s[i+k]
for i, v := range p[:k] {
if i < k/2 {
sm += v
}
sr += v
}
ans := math.MaxInt
for i, v := range p[:m-k+1] {
ans = min(ans, sl+sr-sm*2-p[i+k/2]*(k%2))
sl += v
sm += p[i+k/2]
sr += p[i+k]
}
return ans
}
func min(a, b int) int { if b < a { return b }; return a }
cpp 解法, 执行用时: 96 ms, 内存消耗: 107.4 MB, 提交时间: 2022-12-18 13:45:13
class Solution {
public:
int minMoves(vector<int> &nums, int k) {
int n = nums.size(), m = 0;
for (int i = 0; i < n; ++i)
if (nums[i]) {
nums[m] = i - m;
++m;
}
if (m == n) return 0; // 全部都是 1
auto &p = nums;
int sl = 0; // s[i]
int sm = accumulate(p.begin(), p.begin() + k / 2, 0); // s[i+k/2]
int sr = accumulate(p.begin(), p.begin() + k, 0); // s[i+k]
int ans = INT_MAX;
for (int i = 0; i <= m - k; ++i) {
ans = min(ans, sl + sr - sm * 2 - p[i + k / 2] * (k % 2));
sl += p[i];
sm += p[i + k / 2];
sr += p[i + k];
}
return ans;
}
};
java 解法, 执行用时: 4 ms, 内存消耗: 50.5 MB, 提交时间: 2022-12-18 13:44:58
class Solution {
public int minMoves(int[] nums, int k) {
int n = nums.length, m = 0;
for (int i = 0; i < n; ++i)
if (nums[i] != 0) {
nums[m] = i - m;
++m;
}
if (m == n) return 0; // 全部都是 1
int[] p = nums;
int sl = 0, sm = 0, sr = 0; // s[i] s[i+k/2] s[i+k]
for (int i = 0; i < k; ++i) {
if (i < k / 2) sm += p[i];
sr += p[i];
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i <= m - k; ++i) {
ans = Math.min(ans, sl + sr - sm * 2 - p[i + k / 2] * (k % 2));
sl += p[i];
sm += p[i + k / 2];
sr += p[i + k];
}
return ans;
}
}
python3 解法, 执行用时: 244 ms, 内存消耗: 20.4 MB, 提交时间: 2022-12-18 13:44:43
class Solution:
def minMoves(self, nums: List[int], k: int) -> int:
m = 0
for i, p in enumerate(i for i, x in enumerate(nums) if x):
nums[i] = p - i
m += 1
if m == len(nums): return 0 # 全部都是 1
ans, p = inf, nums
sl, sm, sr = 0, sum(p[:k // 2]), sum(p[:k]) # s[i] s[i+k//2] s[i+k] 忽略切片开销
for i in range(m - k + 1):
ans = min(ans, sl + sr - sm * 2 - p[i + k // 2] * (k % 2))
sl += p[i]
sm += p[i + k // 2]
sr += p[i + k]
return ans
golang 解法, 执行用时: 108 ms, 内存消耗: 9.4 MB, 提交时间: 2022-12-18 13:44:21
func minMoves(nums []int, k int) int {
p := []int{}
for i, v := range nums {
if v != 0 {
p = append(p, i-len(p))
}
}
m := len(p)
s := make([]int, m+1) // p 的前缀和
for i, v := range p {
s[i+1] = s[i] + v
}
ans := math.MaxInt
for i, v := range s[:m-k+1] { // p[i] 到 p[i+k-1] 中所有数到 p[i+k/2] 的距离之和，取最小值
ans = min(ans, v+s[i+k]-s[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 }
cpp 解法, 执行用时: 96 ms, 内存消耗: 115.3 MB, 提交时间: 2022-12-18 13:44:09
class Solution {
public:
int minMoves(vector<int> &nums, int k) {
vector<int> p;
for (int i = 0; i < nums.size(); ++i)
if (nums[i]) p.push_back(i - p.size());
int m = p.size(), s[m + 1];
s[0] = 0;
partial_sum(p.begin(), p.end(), s + 1); // p 的前缀和
int ans = INT_MAX;
for (int i = 0; i <= m - k; ++i) // p[i] 到 p[i+k-1] 中所有数到 p[i+k/2] 的距离之和，取最小值
ans = min(ans, s[i] + s[i + k] - s[i + k / 2] * 2 - p[i + k / 2] * (k % 2));
return ans;
}
};
java 解法, 执行用时: 10 ms, 内存消耗: 49.1 MB, 提交时间: 2022-12-18 13:43:57
class Solution {
public int minMoves(int[] nums, int k) {
var p = new ArrayList<Integer>();
for (int i = 0; i < nums.length; ++i)
if (nums[i] != 0) p.add(i - p.size());
int m = p.size();
int[] s = new int[m + 1]; // p 的前缀和
for (int i = 0; i < m; i++)
s[i + 1] = s[i] + p.get(i);
int ans = Integer.MAX_VALUE;
for (int i = 0; i <= m - k; ++i) // p[i] 到 p[i+k-1] 中所有数到 p[i+k/2] 的距离之和，取最小值
ans = Math.min(ans, s[i] + s[i + k] - s[i + k / 2] * 2 - p.get(i + k / 2) * (k % 2));
return ans;
}
}
python3 解法, 执行用时: 204 ms, 内存消耗: 22.8 MB, 提交时间: 2022-12-18 13:43:42
# 中位数贪心
class Solution:
def minMoves(self, nums: List[int], k: int) -> int:
p = [q - i for i, q in enumerate(i for i, x in enumerate(nums) if x)]
s = list(accumulate(p, initial=0)) # p 的前缀和
return min(s[i] + s[i + k] - s[i + k // 2] * 2 - p[i + k // 2] * (k % 2)
for i in range(len(p) - k + 1)) # p[i:i+k] 中所有数到 p[i+k//2] 的距离之和，取最小值