LeetCode 2134. 最少交换次数来组合所有的 1 II

一、题目描述

交换 定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。
环形 数组是一个数组，可以认为 第一个 元素和 最后一个 元素 相邻 。
给你一个 二进制环形 数组nums ，返回在 任意位置 将数组中的所有 1 聚集在一起需要的最少交换次数。
输入：nums = [0,1,0,1,1,0,0]
输出：1

  来源：力扣（LeetCode）2134. 最少交换次数来组合所有的 1 II

二、解题报告

1、思路分析

（1）看到环形，可以将数组扩容，形成两倍的数组
（2）统计数组中 1 的个数，作为一个滑动窗口
（3）窗口从0开始，一直滑，期间记录窗口中 1 最多的情况，即窗口中 0 的个数是需要交换的次数
（4）返回最多的 1 时的 0 的个数。

2、时间复杂度

_O(n)_

3、代码详解

int minSwaps(int* nums, int n){
    int copy[200010];
    int i,ans=0,sum=0;
    int windows=0;
    for(i=0;i<n;i++){
    	//统计1的个数
        if(nums[i]==1) sum++;
    }
    for(i=0;i<2*n;i++){
    	//数组扩容，%实现循环
        copy[i]=nums[i%n];
    }
    for(i=0;i<sum;i++){
    	//初始化窗口
        windows+=copy[i];
    }
    ans=windows;
    for(int i=0;i<n;i++){
    	//窗口滑动
        windows-=copy[i];
        windows+=copy[i+sum];
        if(windows>ans){
            ans=windows;
        }
    }
    //返回零的值
    return sum-ans;
}

打赏