重新排列数组，使'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插槽中）。在第二遍中，旧号码被删除。