题目描述
交换 定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。
环形 数组是一个数组，可以认为 第一个 元素和 最后一个 元素 相邻 。
给你一个 二进制环形 数组 nums ，返回在 任意位置 将数组中的所有 1 聚集在一起需要的最少交换次数。
示例 1：
输入：nums = [0,1,0,1,1,0,0]
输出：1
解释：这里列出一些能够将所有 1 聚集在一起的方案：
[0,0,1,1,1,0,0] 交换 1 次。
[0,1,1,1,0,0,0] 交换 1 次。
[1,1,0,0,0,0,1] 交换 2 次（利用数组的环形特性）。
无法在交换 0 次的情况下将数组中的所有 1 聚集在一起。
因此，需要的最少交换次数为 1 。
示例 2：
输入：nums = [0,1,1,1,0,0,1,1,0]
输出：2
解释：这里列出一些能够将所有 1 聚集在一起的方案：
[1,1,1,0,0,0,0,1,1] 交换 2 次（利用数组的环形特性）。
[1,1,1,1,1,0,0,0,0] 交换 2 次。
无法在交换 0 次或 1 次的情况下将数组中的所有 1 聚集在一起。
因此，需要的最少交换次数为 2 。
示例 3：
输入：nums = [1,1,0,0,1]
输出：0
解释：得益于数组的环形特性，所有的 1 已经聚集在一起。
因此，需要的最少交换次数为 0 。
提示：
1 <= nums.length <= 105nums[i] 为 0 或者 1
解法
方法一：滑动窗口
我们先统计数组中 $1$ 的个数，记为 $k$，那么题目实际上就是求一个长度为 $k$ 的环形子数组，使得子数组中 $1$ 的个数最多，那么最少交换次数就是 $k$ 减去子数组中 $1$ 的个数最多的那个子数组中 $1$ 的个数。
我们可以使用滑动窗口来解决这个问题，首先统计数组中前 $k$ 个元素中 $1$ 的个数，记为 $cnt$，然后我们维护一个长度为 $k$ 的滑动窗口，每次向右移动一个位置，更新 $cnt$，同时更新最大的 $cnt$ 值，即 $mx = \max(mx, cnt)$，最后答案就是 $k - mx$。
时间复杂度 $O(n)$，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(1)$。
| class Solution:
def minSwaps(self, nums: List[int]) -> int:
k = nums.count(1)
mx = cnt = sum(nums[:k])
n = len(nums)
for i in range(k, n + k):
cnt += nums[i % n]
cnt -= nums[(i - k + n) % n]
mx = max(mx, cnt)
return k - mx
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution {
public int minSwaps(int[] nums) {
int k = Arrays.stream(nums).sum();
int n = nums.length;
int cnt = 0;
for (int i = 0; i < k; ++i) {
cnt += nums[i];
}
int mx = cnt;
for (int i = k; i < n + k; ++i) {
cnt += nums[i % n] - nums[(i - k + n) % n];
mx = Math.max(mx, cnt);
}
return k - mx;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution {
public:
int minSwaps(vector<int>& nums) {
int k = accumulate(nums.begin(), nums.end(), 0);
int n = nums.size();
int cnt = accumulate(nums.begin(), nums.begin() + k, 0);
int mx = cnt;
for (int i = k; i < n + k; ++i) {
cnt += nums[i % n] - nums[(i - k + n) % n];
mx = max(mx, cnt);
}
return k - mx;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | func minSwaps(nums []int) int {
k := 0
for _, x := range nums {
k += x
}
cnt := 0
for i := 0; i < k; i++ {
cnt += nums[i]
}
mx := cnt
n := len(nums)
for i := k; i < n+k; i++ {
cnt += nums[i%n] - nums[(i-k+n)%n]
mx = max(mx, cnt)
}
return k - mx
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13 | function minSwaps(nums: number[]): number {
const n = nums.length;
const k = nums.reduce((a, b) => a + b, 0);
let cnt = k - nums.slice(0, k).reduce((a, b) => a + b, 0);
let min = cnt;
for (let i = k; i < n + k; i++) {
cnt += nums[i - k] - nums[i % n];
min = Math.min(min, cnt);
}
return min;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13 | function minSwaps(nums) {
const n = nums.length;
const k = nums.reduce((a, b) => a + b, 0);
let cnt = k - nums.slice(0, k).reduce((a, b) => a + b, 0);
let min = cnt;
for (let i = k; i < n + k; i++) {
cnt += nums[i - k] - nums[i % n];
min = Math.min(min, cnt);
}
return min;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | impl Solution {
pub fn min_swaps(nums: Vec<i32>) -> i32 {
let k: i32 = nums.iter().sum();
let n: usize = nums.len();
let mut cnt: i32 = 0;
for i in 0..k {
cnt += nums[i as usize];
}
let mut mx: i32 = cnt;
for i in k..(n as i32) + k {
cnt += nums[(i % (n as i32)) as usize]
- nums[((i - k + (n as i32)) % (n as i32)) as usize];
mx = mx.max(cnt);
}
return k - mx;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | public class Solution {
public int MinSwaps(int[] nums) {
int k = nums.Sum();
int n = nums.Length;
int cnt = 0;
for (int i = 0; i < k; ++i) {
cnt += nums[i];
}
int mx = cnt;
for (int i = k; i < n + k; ++i) {
cnt += nums[i % n] - nums[(i - k + n) % n];
mx = Math.Max(mx, cnt);
}
return k - mx;
}
}
|
方法二：前缀和