和PAT书上的思路不一样。我使用了map，费内存是真的。但是换来了运行时间。
使用map的思路是这样的。
原来用数组，下标里面存值。
用map则是key是值，value是原来数组的下标，即map<值，下标>
这样就O(1)访问了。
#include<map> #include<iostream> #include<algorithm> using namespace std; int main(){ int n; scanf("%d", &n); map<int, int> imap; int num = -1; for(int i=0; i<n; ++i){ int temp; scanf("%d", &temp); if(temp!=i) num++; imap[temp]=i; } int index = 0; int cnt = 0; int k=1; while(num>0){ while(imap[0]!=0){ swap(imap[0],imap[imap[0]]); cnt++; num--; } for(int i=k;i<n;++i){ if(imap[i]!=i){ swap(imap[0], imap[i]); cnt++; k=i+1; break; } } } printf("%d\n", cnt); return 0; }
