主題
題目連結：
題目意譯：
你被給定一個索引值從 0 開始數的正整數陣列 nums 以及一個正整數 limit。
在一次操作中，你可以選擇任兩個索引值 i 和 j 並將 nums[i] 與 nums[j] 交換，前提是 |nums[i] - nums[j]| ≦ limit。
回傳執行上述操作若干次後可以得到的字典序最小之陣列。
一個陣列 a 字典序小於另一個陣列 b，代表著在 a 和 b 第一個不同的位置，陣列 a 對應的元素比陣列 b 對應的元素小。例如說，陣列 [2,10,3] 字典序小於 [10,2,3]，因為它們不同於索引值 0 且 2 < 10。
限制：
1 ≦ nums.length ≦ 10 ^ 5
1 ≦ nums[i] ≦ 10 ^ 9
1 ≦ limit ≦ 10 ^ 9
範例測資：
範例 1：
輸入： nums = [1,5,3,9,8], limit = 2
輸出： [1,3,5,8,9]
解釋： 執行操作 2 次：
- 將 nums[1] 與 nums[2] 交換。陣列變為 [1,3,5,9,8]
- 將 nums[3] 與 nums[4] 交換。陣列變為 [1,3,5,8,9]
我們無法藉由執行更多操作來得到字典序更小的陣列。
注意到可以藉由不同的操作是有可能得到相同結果的。
範例 2：
輸入： nums = [1,7,6,18,2,1], limit = 3
輸出： [1,6,7,18,1,2]
解釋： 執行操作 3 次：
- 將 nums[1] 與 nums[2] 交換。陣列變為 [1,6,7,18,2,1]
- 將 nums[0] 與 nums[4] 交換。陣列變為 [2,6,7,18,1,1]
- 將 nums[0] 與 nums[5] 交換。陣列變為 [1,6,7,18,1,2]
我們無法藉由執行更多操作來得到字典序更小的陣列。
範例 3：
輸入： nums = [1,7,28,19,10], limit = 3
輸出： [1,7,28,19,10]
解釋： [1,7,28,19,10] 本身就是我們能得到的字典序最小之陣列，因為我們無法在任何兩個索引值上執行操作。
解題思維：
由於交換的規則跟數值差有關，因此我們先觀察一下一些數字。
假設現在有 a 、 b 、 c 三個數字，其中 |a - b| ≦ limit 且 |b - c| ≦ limit（也就是說相鄰的數字差不超過 limit）。則我們可以看到這三個數字可以排成任何順序。
同樣地，四個數字 a 、 b 、 c 、 d，其中 |a - b| ≦ limit 、 |b - c| ≦ limit 且 |c - d| ≦ limit。則我們可以將這四個數字排成任意順序。以此類推。
因此我們可以先將 nums 複製一份並為每一個元素及其原本的索引值「綁在一起」，然後按照元素數值大小由小排到大（稱此複製陣列為 A）。
可以看到 A[0] 會跟 A[1] 、 A[2] 、 …… 、 A[i] 等等形成一個如上面提及的數字群，即 A[0] ～ A[i] 之間兩兩相鄰代表的數值差不超過 limit（注意這邊的 i 是取最大的那一個）。
而為了最小化字典序，因此 A[0] ~ A[i] 代表的數值應在它們代表的索引值上由小排到大。因此可以從 A[0] ~ A[i] 取出數值和索引值，將數值和索引值分別由小排到大。排序後第一個數值應放到排序後的第一個索引值、排序後第二個數值應放到排序後的第二個索引值……以此類推。
並且我們可以看到 A[0] ~ A[i] 跟其他數字群是完全獨立的，所以我們可以對其他數字群做相同的事情而不干擾到彼此。
因此掃過一次 A 便可以找到所有數字群，並按排序後的數值和索引值來重新排列 nums 中的數字。最後得到的新 nums 即為所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
