题目描述
给定一个整数数组 nums
和一个整数 k
。nums
仅包含 0
和 1
。每一次移动,你可以选择 相邻 两个数字并将它们交换。
返回使 nums
中包含 k
个 连续 1 的 最少 交换次数。
样例
输入:nums = [1,0,0,1,0,1], k = 2
输出:1
解释:在第一次操作时,nums 可以变成 [1,0,0,0,1,1] 得到连续两个 1。
输入:nums = [1,0,0,0,0,0,1,1], k = 3
输出:5
解释:通过 5 次操作,最左边的 1 可以移到右边直到 nums 变为 [0,0,0,0,0,1,1,1]。
输入:nums = [1,1,0,1], k = 2
输出:0
解释:nums 已经有连续 2 个 1 了。
限制
1 <= nums.length <= 10^5
nums[i]
要么是0
,要么是1
。1 <= k <= sum(nums)
算法
(决策值单调) $O(n)$
- 先考虑在常数时间内,计算出一个含有 $k$ 个 1 的区间,在某个 1 的位置聚合起来的代价。有一种方法是通过等差数列求和与区间和的差值快速计算。
- 容易发现,对于某一个区间,我们选定 1 所付出的代价是会先单调递减然后单调递增的数列,但这个性质不能用来强行二分或者三分来求解最低点,因为递减和递增都是非严格的。
- 但这里还有另外一个性质,就是下一个连续 $k$ 个 1 的区间的最低点一定是大于等于当前连续 $k$ 个 1 的最低点。利用这个性质,可以每次比较当前决策点与下一个决策点之间的大小关系,当当前决策点大于等于下一决策点时,果断移动到下一个决策点。
- 遍历过所有 $k$ 个 1 的区间,找到最小值。
时间复杂度
- 预处理需要 $O(n)$ 的时间,遍历区间找最小值需要 $O(n)$ 的时间。
- 故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储预处理的数组。
C++ 代码
#define LL long long
class Solution {
private:
LL calc(int l, int r, int m,
const vector<int> &pos, const vector<LL> &s) {
int lc = m - l, rc = r - m;
int st = pos[m] - lc, ed = pos[m] + rc;
LL ls = (LL)(st + pos[m] - 1) * lc / 2 - (s[m - 1] - s[l - 1]);
LL rs = s[r] - s[m] - (LL)(pos[m] + 1 + ed) * rc / 2;
return ls + rs;
}
public:
int minMoves(vector<int>& nums, int k) {
const int n = nums.size();
vector<int> pos(1, 0);
int m = 0;
for (int i = 0; i < n; i++)
if (nums[i] == 1) {
pos.push_back(i);
m++;
}
vector<LL> s(m + 1, 0);
for (int i = 1; i <= m; i++)
s[i] = s[i - 1] + pos[i];
LL ans = INT_MAX;
for (int i = k, j = 1; i <= m; i++) {
while (j < i - k + 1) j++;
while (j < m - 1 &&
calc(i - k + 1, i, j, pos, s) >= calc(i - k + 1, i, j + 1, pos, s))
j++;
ans = min(ans, calc(i - k + 1, i, j, pos, s));
}
return ans;
}
};
您的 $Latex$ 好像挂了qwq
啊哈?
啊我记得上次从主页看到您的题解,好像有的地方显示 $\color{red}{\text{MathExpressionError}}$
反正现在好了