Castria的博客
0%

LeetCode 1703.得到连续 K 个 1 的最少相邻交换次数

发表于

题意

给定一个仅包含$0$和$1$的数组，仅能交换其中相邻的两个数字，问至少多少次这样的操作可以使得至少$k$个$1$相邻。

题解

取数组中任意$k$个相距最近的$1$，设它们出现的下标分别为$a_1,a_2,…,a_k.$考虑将它们交换多少次可以使得它们聚成连续的$k$个$1$。有这样一个常用结论：对于数轴上的点$a_1,a_2,…,a_k$，使它们移动到一处的最小代价当它们都移动到该序列的中位数时取得（若长度为偶数，左边的和右边的均可）。按照这个结论，我们要将所有的$1$都移动到$a_1,a_2,…,a_k$的中位数旁边。先讨论

$(1)$长度$k=2n+1$即$k$为奇数的情况:
要将$a_1,a_2,…,a_{n+1},…,a_{2n},a_{2n+1}$移动到$a_{n+1}$处，
首先将$a_{n},a_{n+2}$移动到$a_{n+1}$的左右两边，其消耗为$(a_{n+1}-a_n-1)+(a_{n+2}-a_{n+1}-1);$
再将$a_{n-1},a_{n+3}$分别移动到$a_{n},a_{n+2}$的两边，消耗为$(a_{n+1}-a_{n-1}-2)+(a_{n+3}-a_{n+1}-2);$
以此类推，可以求得消耗之和为
$\sum_{i=1}^{2n+1}|a_{n+1}-a_{i}|-2(1+2+…+n)=\sum_{i=1}^{2n+1}|a_{n+1}-a_{i}|-n(n+1).$

$(1)$长度$k=2n$，即$k$为偶数的情况:
用与奇数的情况类似的方法推导，可以得到消耗之和为$\sum_{i=1}^{2n}|a_{n+1}-a_{i}|-2(1+2+…+(n-1))-n=\sum_{i=1}^{2n}|a_{n+1}-a_{i}|-n^2.$

因此只需用一个滑动窗口从序列的左边扫到右边，使得窗口中始终含有$k$个$1$，同时维护消耗值即可。观察到消耗值中$n(n+1)$(或$n^2$)与序列中的值无关，最后减去即可，于是重点就在于维护绝对值之和的项(记为$abssum$)。

考虑移动过程中$abssum$的变化：

先讨论$k=2n+1$时的情况。设序列由
$a_1,a_2,…,a_{2n+1}$滑动到$a_2,a_3,…,a_{2n+1},a_{2n+2}.$

原来的$abssum_0=(a_{n+1}-a_1)+(a_{n+1}-a_2)+…+(a_{n+1}-a_n)+(a_{n+2}-a_{n+1})+…+(a_{2n+1}-a_{n+1});$

滑动后的$abssum’=(a_{n+2}-a_2)+(a_{n+2}-a_3)+…+(a_{n+2}-a_{n+1})+(a_{n+3}-a_{n+2})+…+(a_{2n+2}-a_{n+2}).$
两式相减得

$abssum’-abssum_0=a_{2n+2}+a_1-a_{n+1}-a_{n+2},$即两边的值减去新旧中位数之和。

同理可以求得，当$k=2n$时，$abssum’-abssum_0=a_{2n+1}+a_1-2a_{n+1},$即两边的值减去原序列右边的中位数的二倍。（这里在推导时，$abssum_0$用的中位数和$abssum’$用的中位数都是$a_{n+1}$）因此只需在滑动过程中维护新旧中位数、新添加进来的$1$和即将被删掉的$1$即可。由于各个变量至多从$0$移动到$num.size()-1,$故时间复杂度$O(n).$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
    int minMoves(vector<int>& nums, int k) {
        int mid;
        int count = 0,l = 0,r = -1,abssum = 0,ans = INT_MAX;
        //count:计数1的个数到达k;
        //l,r:滑动窗口的边界
        //abssum:如上文
        //ans:答案

        //初始化向窗口中加入k个最左边的1
        while(count != k) {
            r++;
            if(nums[r] == 1) {
                count++;
                if(count == 1) {//初始化中位数位置
                    mid = r;
                    continue;
                }
                if(count % 2 == 1) {//偶数个1变为奇数个1,中位数要右移到下一个1
                    mid++;
                    while(nums[mid] != 1) mid++;
                }
            }
        }
        while(nums[l] != 1) l++;//使l指向最左的1

        //初始化abssum
        for(int i = 0; i <= r; i++) {
            if(nums[i] == 1) abssum += abs(i - mid);
        }
        ans = min(ans, abssum);

        //开始滑动
        while(r < nums.size()) {
            r++;
            //找到下一个1
            while(r < nums.size() && nums[r] != 1) r++;
            if(r >= nums.size()) break;
            //保存旧的中位数和旧的最左边1
            int mid0 = mid,l0 = l;
            mid++,l++;

            //找到下一个中位数；去掉窗口中最左边的1
            while(nums[mid] != 1) mid++;
            while(nums[l] != 1) l++;

            //维护abssum
            if(k%2 == 0) abssum += r + l0 - 2 * mid;
            else abssum += r + l0 - mid - mid0;

            ans = min(ans, abssum);
        }
        //最后减掉含n的式子:在奇数/偶数情况下等价于n(n+1) / n*n.
        int bias = (k / 2) * ((k + 1) / 2);
        return ans - bias;
    }
};