查找数组中重复次数最多的模数

Question

谁能给我解释一下这是怎么做到的？这是我试图理解的代码片段：

// Iterate though input array, for every element
    // arr[i], increment arr[arr[i]%k] by k where k is less than of equal to number of elements
    // ie. k <= n
    for (int i = 0; i< n; i++)
        arr[(arr[i]%k)] += k;

    // Find index of the maximum repeating element
    int max = arr[0], result = 0;
    for (int i = 1; i < n; i++)
    {
        if (arr[i] > max)
        {
            max = arr[i];
            result = i;
        }
    }

我意识到，当我们第一次遍历数组时，我们

取我们迭代模 k 的每个元素的值。
以此为索引；
在索引处取一个元素，然后增加 k.

完成后，最高数字元素的索引就是我们正在寻找的最频繁的数字。

我理解这些步骤，但我不理解其中的逻辑，尤其是关于模数和索引与值的逻辑。任何解释将不胜感激！

Answer 1

只有当保证 0 <= arr[i] < k 或 arr[i] 的范围位于 k 个值的区间内时，该解决方案才有效。

该算法使用相同的数组 (arr) 作为频率哈希图来存储特定值的出现次数，尽管使用模运算。任何数字在被除数递增时每次都会给出相同的余数。每次找到一个出现时，arr[i] % k 处的元素都会增加 k。这类似于将频率散列图递增 1。在迭代结束时，所有元素将递增 (number of times value occurs) * k。找到最大元素，然后会给你出现次数最多的元素。

此算法中有您未提及的假设：

0 < arr[i] <= k
k <= n
如果重复次数最多的元素之间存在平局，则选取具有最大值的元素。
如果 (count of occurences) * k + arr[i] 大于 INT_MAX，结果可能会溢出。

查找数组中重复次数最多的模数

Modulo in finding most repeated number in array

arrays

max

repeat

data-structures