1067 Sort with Swap(0, i) (25 point(s)) 超时情况

原题链接
一开始兴高采烈写完，以为很简单就ac了，结果蹦出两个超时。由于我基本用的scanf，所以输入数据应该不会导致超时，一定是中间某个步骤复杂度太大导致超时了。所以我把目光放在的两个循环上。
很显然，我中间用到了两个嵌套循环，复杂度是二次方级，我需要优化一下降低复杂度。我想了很久没有想到解决的办法，觉得不历遍数组是不行的（最搞笑的是我尝试甚至还用了随机数，结果全部超时）。
后来我翻看了下算法笔记，提到利用已swap数据的不可移动性存储位置。一开始我抱有疑惑，觉得不可行，依然需要历遍数组，但后来仔细思考后发现的确是个很好的办法，并没有漏洞，并且很好地将复杂度降低了。在这里我简单总结下。
让k从1开始，向前走，慢慢递增，直到遇见第一个没有回归本位的数，再记录下来它的位置（就像是一辆车向前走，停在遇到的一个障碍上并记录位置）。在算法中我们不会在移动以归位的数字，因此已归位的数字就像平坦的路一样，车已经走过的路不会突然消失。接下来的工作就是移除障碍（就是令其归位后再令k++），车从刚刚记录的位置继续往前走，直到下一个障碍，记录，清除障碍……车不需要回到路的一开头重新开到障碍前，这就省下了很多路程。
下面给出我自己的实现代码。

#include<stdio.h>
#include<iostream>
using namespace std;

int main() {
	int number = 0;
	int count = 0;
	int temp = 0;
	int j = 0;
	int k = 1;
	int a[100010] = { 0 };
	int hashTable[100010] = { 0 };
	cin >> number;
	for (int i = 0; i < number; i++) {
		scanf("%d", &a[i]);
		hashTable[a[i]] = i;
		if (a[i] == 0)
			temp = i;
	}
	for (int i = 0; ; i++) {
		int exc = 0;
		
		if (a[0] == 0) {
			
			for (j = k; j < number; j++) {
				if (a[j] == j)
					continue;
				else {
					k = j + 1;
					a[0] = a[j];
					a[j] = 0;
					count++;
					temp = j;
					hashTable[a[0]] = 0;
					hashTable[0] = j;
					break;
				}
			}
			if (temp == 0)
				break;
		}

		exc = hashTable[temp];
		a[exc] = 0;
		a[temp] = temp;
		hashTable[temp] = temp;
		hashTable[0] = exc;
		count++;
		temp = exc;
		
	}
	cout << count;
}