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、代码详解

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
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;
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2021-2023 lucky_dog
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信