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

Narendra Kumar

更新时间： 2020年1月10日

119次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习