Rust 力扣 - 2134. 最少交换次数来组合所有的 1 II
文章目录
- 题目描述
- 题解思路
- 题解代码
- 题目链接
题目描述
题解思路
我们首先计算数组中长度为0的1的个数k
我们需要遍历长度为k的窗口，找到窗口中0的数量的最小值即为答案
需要注意的是数组是环形的，我们的窗口也应该是环形的
题解代码
impl Solution {
pub fn min_swaps(nums: Vec<i32>) -> i32 {
let mut k = 0;
for num in &nums {
k += num;
}
let mut cnt = 0;
for i in 0..k as usize {
if nums[i] == 0 {
cnt += 1;
}
}
let mut ans = cnt;
for i in 1..nums.len() {
if nums[i - 1] == 0 {
cnt -= 1;
}
if nums[(i - 1 + k as usize) % nums.len()] == 0 {
cnt += 1;
}
ans = ans.min(cnt);
}
ans as i32
}
}
题目链接
https://leetcode.cn/problems/minimum-swaps-to-group-all-1s-together-ii/