Sponsored
Sponsored
The goal is to find the minimum number of swaps needed to group all 1's together. First, count the total number of 1's, which determines the window size you are interested in. Use the sliding window technique to find the window with the maximum number of 1's. This will ensure that the remaining positions in this window must be filled with 1's by swapping.
Since the array is circular, concatenate the array with itself to simulate the wrap-around. Slide a window of the calculated size and keep track of the maximum number of 1's within this window. To minimize swaps, the window should contain the maximum possible 1's.
Time Complexity: O(n), where n is the size of the array, due to the sliding window.
Space Complexity: O(1), because the space used does not scale with input size.
1#include <iostream>
2#include <vector>
3
4int minSwaps(std::vector<int>& nums) {
5 int totalOnes = 0;
6 for (int num : nums) if (num == 1) totalOnes++;
7
8 int maxOnes = 0, currentOnes = 0;
9 int n = nums.size();
10 for (int i = 0; i < 2 * n; i++) {
11 if (i < totalOnes) currentOnes += nums[i % n];
12 else {
13 currentOnes += nums[i % n];
14 currentOnes -= nums[(i - totalOnes) % n];
}
if (i >= totalOnes - 1) {
maxOnes = std::max(maxOnes, currentOnes);
}
}
return totalOnes - maxOnes;
}
int main() {
std::vector<int> nums = {0, 1, 0, 1, 1, 0, 0};
std::cout << minSwaps(nums) << std::endl;
return 0;
}This C++ solution mirrors the C solution, using a vector to store the binary numbers. It implements the sliding window technique, leveraging the modulo operator to handle the circular nature of the array. This approach allows for determining the minimum swaps by maintaining a window of size equal to the count of 1's.