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