数据结构
网络
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次浏览
广告