資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++中使用最多1次交換獲得固定點的最大數量
問題陳述
給定一個從0到N-1的N個元素的排列。固定點是指值與索引相同的索引，即arr[i] = i。您可以最多進行1次交換。找到您可以獲得的固定點的最大數量。
示例
如果輸入陣列為{0, 1, 2, 3, 4, 6, 5}，則答案為7。
- 為了調整固定點，我們必須交換6和5
- 此後整個陣列都成為固定點，固定點的最大值為7。
演算法
- 建立一個數組pos，它儲存輸入陣列中每個元素的位置
- 現在，我們遍歷陣列並有以下情況：
- 如果a[i] = i。我們可以簡單地增加計數並繼續
- 如果pos[i] = a[i]，這意味著交換這兩個項將使i和a[i]成為固定點，從而使計數增加2。請記住，交換最多隻能執行一次。
- 在遍歷結束時，如果我們沒有進行任何交換，則意味著我們的交換無法使計數增加2，因此現在如果至少有兩個元素不是固定點，我們可以進行交換以使計數增加1，即使其中一個點成為固定點。
示例
#include <bits/stdc++.h>
using namespace std;
int getMaximumFixedPoints(int arr[], int n) {
int i, pos[n], count = 0, swapped = 0;
for (i = 0; i < n; i++)
pos[arr[i]] = i;
for (i = 0; i < n; i++) {
if (arr[i] == i) {
count++;
} else if (swapped == 0 && pos[i] == arr[i]) {
count += 2;
swapped = 1;
}
}
if (swapped == 0 && count < n - 1) {
count++;
}
return count;
}
int main() {
int arr[] = {0, 1, 2, 3, 4, 6, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum value of fixed point = " << getMaximumFixedPoints(arr, n) << endl;
return 0;
}輸出
編譯並執行上述程式時，會生成以下輸出：
Maximum edges = 7
更新時間： 2020年1月10日
119次瀏覽
廣告