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]は、2つの項を交換するとiとa [i]が固定小数点になるため、カウントが2増えることを意味します。交換は最大で1回しか実行できないことに注意してください。 。
• トラバーサルの最後に、スワップを行わなかった場合、スワップでカウントを2増やすことができなかったことを意味します。したがって、固定小数点ではない要素が少なくとも2つある場合は、次のことができます。スワップを行ってカウントを1増やします。つまり、これらのポイントの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