PAT A1067 Sort with Swap(0, i)

题目链接

解题思路

利用散列的思想将输入数据保存到一个数组，索引即数据，对应的值是此数的位置。使用no找出这串数中除了0以外不在本位的数。然后每次根据0的位置nums[0]找到对应的数nums[nums[0]]的位置，交换两数的位置。中间可能0会回到0位，那么就是用一个变量k，从1开始找到第一个最小的不在本位的数。记录交换次数，最后输出即可。

注意

1、如果0归位的时候，每次都是从头开始找不在本位的数，会导致运行超时，定义一个全局变量k，利用每个移回本位的数在后续操作不在变，所以可以每次找k后面的数。

2、no必须除0以外，因为是用0进行交换，交换次数就是除0以外不在本位的个数。

代码

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int INF = 1e9 + 10;
const int maxn=1e5+10;
int n,nums[maxn];
void swap1(int &a, int &b) {
    int t = a;
    a = b;
    b = t;
}

int main() {
    scanf("%d", &n);
    int x,no=0;//no记录除了0以外不在本位置的个数，因为0要与其他的不在本位的进行交换
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        if(i!=x) no++;
        nums[x]=i;//记录x的位置在i
    }
    int k=1,cnt=0;
    while(no>1){
        while(nums[0]!=0){
            swap1(nums[0],nums[nums[0]]);
            cnt++;
            no--;
        }
        if(nums[0]==0){
           while(k<n){
               if(nums[k]!=k){
                    swap1(nums[0],nums[k]);
                    cnt++;
                    break;
               }
               k++;
           }
        }
    }
    printf("%d",cnt);
    return 0;
}