查找数组中整数的众数

Question

对于这个问题，我将编写一个名为 mode 的方法，该方法返回整数数组中出现频率最高的元素。假设数组至少有一个元素，并且数组中的每个元素都有一个介于 0 和 100 之间的值。通过选择较低的值打破联系。

例如，如果传递的数组包含值 {27, 15, 15, 11, 27}，则您的方法应返回 15。（提示：您可能希望查看本章前面的 Tally 程序以了解如何解决这个问题呢。）

我在查看特定输入出了什么问题时遇到了问题。例如：

mode({27, 15, 15, 27, 11, 11, 11, 14, 15, 15, 16, 19, 99, 100, 0, 27}) 返回 15，这是正确的，但是 mode({1, 1, 2, 3, 3}) 当它应该是 1 时返回 3。

这是代码：

public static int mode(int[] input) {
    int returnVal = input[0]; // stores element to be returned
    int repeatCount = 0; // counts the record number of repeats
    int prevRepCnt = 0; // temporary count for repeats

    for (int i=0; i<input.length; i++) { // goes through each elem

        for (int j=i; j<input.length; j++) { // compares to each elem after the first elem

            if (i != j && input[i] == input[j]) { // if matching values
                repeatCount++; // gets the repeat count

                if (repeatCount>=prevRepCnt) { // a higher count of repeats than before
                    returnVal=input[i]; // return that element
                }
                prevRepCnt = repeatCount; // Keeps the highest repeat record
            }
            repeatCount=0; // resets repeat Count for next comparison
        }
    }
    return returnVal;
}

Answer 1

这里有一个更简单的方法来解决这个问题。创建一个大小为 101 的名为 count 的数组。索引 (0-100) 表示您正在计算的数字。遍历输入数组并计算每个数字的出现次数。最后，比较计数以找到出现最多的计数（并列到较低的数字）：

public static int mode(int[] input) {

    int[] count = new int[101];

    //count the occurrences
    for (int i=0; i < input.length; i++) {
        count[input[i]]++;
    }

    //go backwards and find the count with the most occurrences
    int index = count.length-1;
    for (int i=count.length-2; i >=0; i--) {
        if (count[i] >= count[index])
            index = i;
    }

    return index;
}

Answer 2

我最近分析了四种计算数组众数的方法：

• 如果数组中的数字范围很小，则使用计数排序 - O(N) 时间、(N) 空间但非常高效。该解决方案直接适用于您所询问的问题，因为数组中只有 101 个可能的值。
• 哈希表中数组中的索引元素 - O(N) 时间，O(N) 空间。如果值取自较大范围（例如所有整数），则此解决方案适用。
• 对数组进行排序，然后计算连续的相等元素 - O(NlogN) 时间，O(1) 空间。如果数组太大而无法构建索引，则适用此解决方案。
• 对数组进行部分排序，但跳过小于当前候选的分区 - O(NlogN) 时间、O(1) 空间，但比对数组完全排序效率更高，因为将跳过许多分区。

您可以在本文中找到所有四种方法的源代码（尽管是 C# 的）和性能比较：Finding Mode of an Array