資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中將所有小於等於k的元素放在一起所需的最小交換次數
問題陳述
給定一個包含n個正整數的陣列和一個數字k。找到將所有小於或等於k的數字放在一起所需的最小交換次數。
示例
如果輸入陣列為{1, 5, 4, 7, 2, 10}且k = 6，則需要1次交換，即交換元素7和2。
演算法
- 計算所有小於或等於‘k’的元素。假設計數為‘cnt’
- 使用雙指標技術處理長度為‘cnt’的視窗，每次跟蹤此範圍內有多少個元素大於‘k’。假設總數為‘outOfRange’。
- 對長度為‘cnt’的每個視窗重複步驟2，並在其中取‘outOfRange’計數的最小值。這將是最終答案。
示例
#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(int *arr, int n, int k) {
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (arr[i] <= k) {
++cnt;
}
}
int outOfRange = 0;
for (int i = 0; i < cnt; ++i) {
if (arr[i] > k) {
++outOfRange;
}
}
int result = outOfRange;
for (int i = 0, j = cnt; j < n; ++i, ++j) {
if (arr[i] > k) {
--outOfRange;
}
if (arr[j] > k) {
++outOfRange;
}
result = min(result, outOfRange);
}
return result;
}
int main() {
int arr[] = {1, 5, 4, 7, 2, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 6;
cout << "Minimum swaps = " << getMinSwaps(arr, n, k) <<
endl;
return 0;
}編譯並執行上述程式時，將生成以下輸出：
輸出
Minimum swaps = 1
更新於：2019年12月20日
393 次瀏覽
廣告