本题O(n)做法
查看原帖
本题O(n)做法
1043409
FUN_QAQ楼主2024/1/2 10:18
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
int pos[maxn];
int pre[maxn]; // 记录当前存储值为i的在pos的哪一个位置
int n;
int cnt = 0;
// O(n) 做法
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> pos[i];
        pre[pos[i]] = i;
    }
    for (int i = 1; i <= n; ++i)
    {
        if (pos[i] == i)
        {
            continue;
        }
        int x = pos[i];            // 本来的位置的数值
        int y = pos[pre[i]];       // 要交换的位置的数值
        swap(pos[i], pos[pre[i]]); // 交换到pre的位置
        // 记得更新pre数组
        pre[x] = pre[i];
        ++cnt;
    }
    cout << cnt << endl;
    return 0;
}
2024/1/2 10:18
加载中...