資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中將所有 1 組合到一起所需的最小交換次數
問題陳述
給定一個 0 和 1 的陣列。任務是找出將陣列中所有 1 組合在一起所需的最小交換次數。
例如
如果輸入陣列 = {1, 0, 1, 1, 0, 1}，則需要 1 次交換。即交換第一個 0 和最後一個 1。
演算法
- 計算陣列中 1 的總數
- 如果計數為 x，那麼我們需要找出具有最大 1 個數量的長度為 x 的此陣列的子陣列
- 所需的最小交換次數將是長度為 x 的子陣列中 0 的數量，其中 1 的數量最大
例如
#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(int *arr, int n) {
int oneCnt = 0;
for (int i = 0; i < n; ++i) {
if (arr[i] == 1) {
++oneCnt;
}
}
int x = oneCnt;
int maxOnes = INT_MIN;
int preCompute[n] = {0};
if (arr[0] == 1) {
preCompute[0] = 1;
}
for (int i = 1; i < n; ++i) {
if (arr[i] == 1) {
preCompute[i] = preCompute[i - 1] + 1;
} else {
preCompute[i] = preCompute[i - 1];
}
}
for (int i = x - 1; i < n; ++i) {
if (i == (x - 1)) {
oneCnt = preCompute[i];
} else {
oneCnt = preCompute[i] - preCompute[i - x];
} if (maxOnes < oneCnt) {
maxOnes = oneCnt;
}
}
int swapCnt = x - oneCnt;
return swapCnt;
}
int main() {
int arr[] = {1, 0, 1, 1, 0, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum swap count = " << getMinSwaps(arr, n) << endl;
return 0;
}當您編譯並執行上述程式時。它將生成以下輸出 −
輸出
Minimum swap count = 1
更新日期：2019-12-20
206 次檢視
廣告