1067. Sort with Swap(0, i).md

【PAT A-1067】Sort with Swap(0, i)

题意概述

给定数字${0,1,2,\cdots,N-1}$的任何一种排列，要按升序对它们进行排序。排序过程中只允许使用Swap(0, i)操作，即交换 0 和 i 的位置。例如，要对{4, 0, 2, 1, 3}进行排序，我们可以通过以下方式应用 Swap(0, i)操作：

Swap(0, 1)=> {4, 1, 2, 0, 3}

Swap(0, 3)=> {4, 1, 2, 3, 0}

Swap(0, 4)=> {0, 1, 2, 3, 4}

你需要给出针对给定排列进行排序所需的最少交换次数。

输入输出格式

输入第一行给出一个正整数 N。接下来一行给出 N 个整数。一行中的所有数字都用空格分隔。

只需在一行中打印对给定排列进行排序所需的最小交换次数即可。

数据规模

$$1\le N\le{10}^5$$

算法设计

解决这道题需要使用贪心算法，我们可以使用unordered_map<gg, gg> um存储位置不正确的数字及其所在位置的映射关系。由于每次只能用 0 交换，有两种情况：

1. 0 不在第 0 位，那么 0 如果在第 i 位，而第 i 位本应该是 i，就应该把 0 和 i 数字所在的位置交换；
2. 如果 0 在第 0 位，在 um 中随意找出一个数字与 0 进行交换（为了方便，可以直接选择 um 的第一个数字）。

um 为空时，说明序列有序，结束算法。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, ai;
    cin >> ni;
    unordered_map<gg, gg> um;
    gg p = -1;  //存储0所在位置
    for (gg i = 0; i < ni; ++i) {
        cin >> ai;
        if (ai == 0) {
            p = i;
        } else if (ai != i) {  //把位置不对的数字存入um
            um[ai] = i;
        }
    }
    gg ans = 0;
    while (not um.empty()) {  // um为空，表明序列有序，结束循环
        if (p != 0) {  // 0的位置不是0，交换0与p这两个数字的位置
            gg t = p;
            p = um[p];
            um.erase(t);
        } else {  // 0在位置0处，交换它与um首个数字的位置
            swap(p, um.begin()->second);
        }
        ++ans;
    }
    cout << ans;
    return 0;
}