C ++中最多使用1个交换的最大固定点数
问题陈述
给定N个元素从0到N-1的排列。一个固定点是一个索引，该索引的值与该索引相同，即arr[i]=i。您最多可以进行1次掉期。找到您可以获得的最大固定点数。
示例
如果输入数组为{0，1，2，3，4，6，5}，则答案为7。
要调整定点，我们必须交换6和5
在此整个数组成为固定点并且固定点的最大值为7之后。
算法
创建一个数组pos，以保持每个元素在输入数组中的位置
现在，我们遍历数组并具有以下情况-
如果a[i]=i。我们可以简单地增加计数并继续
如果pos[i]=a[i]，这意味着交换2个项将使i和a[i]成为固定点，因此将计数增加2。请记住，交换最多可以进行一次。
在遍历结束时，如果我们没有进行任何交换，这意味着我们的交换无法将计数增加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