重新排列數組，使'arr [j]'變成'我'，如果'arr [i]'是'j'模

Question

我試圖從geeksforgeek website解決下一個問題。 給定一個大小爲n的數組，其中所有元素都在0到n-1的範圍內，更改arr []的內容以便arr [i] = j變爲arr [j] = i。 只見溶液中使用模數：

在一個掃描 ARR [ARR [I]％N]

+ = N * I 並在接下來的掃描 ARR [I]/= N

他的解釋：

我做了當時這個，我知道，每個位置都會有一個元素小於n因爲它代表排列的指標，對於任何一個數x，使得x小於n，x％n = x基本上當我寫的時候，arr [arr [i]％n]如果arr [i] = j我正在訪問arr [j] 處的元素，現在您會注意到，在此步驟中，我正在使用n * i 遞增每個這樣的元素，我在一個位置存儲了兩個元素， 例如：假設arr [2] = 5和arr [5] = 4並且總共有6個元素 我將使arr [arr [2]％6] = arr [5％6] = arr [5] = 4 + 12即4 + 2 * 6 它等於16現在它包含兩個數字，如果我不想原始數字，即在第一次掃描期間我改變了所有的值，我寫了arr [5]％6 =（4 + 2 * 6）％6 = 4％6 + 2 * 6％6 = 4 + 0 = 4並且在第二次掃描期間，當我想要將數組更新爲最終的結果arr [5]/6 =（4 + 2 * 6）/ 6 = 4/6 + 2 * 6/6 = 0 + 2 = 2我希望這個解釋能夠幫助您，最好

但我無法理解它背後的邏輯/數學。有人可以用數學方法解釋該方法的邏輯嗎？

Answer 1

這裏的訣竅是在一個數組元素中存儲0..n-1範圍內的兩個數字。說如果你想存儲x和y，你實際上將元素設置爲z = n * x + y。您可以通過執行z/n和y來檢索x，方法是執行z％n。

該解決方案現在使用上述技巧將新數字放入數組（在x插槽中），而不會干擾舊數字（仍在y插槽中）。在第二遍中，舊號碼被刪除。