Indexing Sort

  • 有一堆數字，數字的值介於 1~n 之間，數字的個數大概在 n 附近。
  • 盡最大努力做排序，讓 nums[index] = index。
  • 若排序後，仍有 nums[index] != index 非常有可能是問題的答案。

目標

1
2
index 1 2 3 ... n n+1 (n+1個數)
value 1 2 3 ... n 6 (值介於1~n)

思路

1
2
3
4
5
6
7
8
index 1 2 3 4 5 .... n-1 n n+1
ex:   1 3 5 4 2
      1 5 3 4 2  (走到 index 2, 將 value 3 送到正確的位置(index 3) => 3、5 對調
      1 2 3 4 5  (走到 index 2, 將 value 5 送到正確的位置(index 5) => 5、2 對調

index 1 2 3 4 5 6 7 8 ... n-1 n n+1
ex:   1 2 3 4 5 8   8
      1 2 3 4 5 8   8 (走到 index 6, 不用交換 => 已盡最大努力了, 無法交換

程式

1
2
3
4
5
6
7
8
int n = nums.size() - 1;
nums.insert(nums.begin(), 0); // 避免 index 錯位

// nums[i]<=n+1 => nums 多一位，所以nums[i]的範圍也要變化
for(int i = 1; i <= n+1; i++){
    while(nums[i]!=i && nums[i]<=n+1 && nums[i]!=nums[nums[i]])
        swap(nums[i], nums[nums[i]]);
}

補充

筆記