logo标签列表

在数组中寻找整数的众数

javaarraysmode
5
针对这个问题，我需要编写一个名为mode的方法，该方法返回整数数组中出现次数最多的元素。假设数组至少有一个元素，并且数组中的每个元素的值都在0到100之间（包括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})返回3，而不是1。
以下是代码：
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;
}
5个回答
4

这里有一个更简单的方法来解决这个问题。创建一个大小为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;
}
2
这是一个非常简洁的解决方案，但它限制了您可以使用的值的范围。您可以使用变量代替101，但假设最大数字非常大，比如347616。计数数组将因此占用大量内存，没有任何好处。 - Jason210
4
我最近分析了四种计算数组众数的方法：
  • 如果数组中数字的范围很小，则使用计数排序 - O（N）时间，O（N）空间，但非常高效。该解决方案可以直接应用于您所问的问题，因为数组中只有101个可能的值。
  • 在哈希表中对数组元素进行索引 - O（N）时间，O（N）空间。如果值取自一个大范围，例如所有整数，则可以使用此解决方案。
  • 对数组进行排序，然后计算连续相等的元素 - O（NlogN）时间，O（1）空间。如果数组太大而无法构建索引，则可以使用此解决方案。
  • 部分排序数组，但跳过当前候选项以下的分区 - O（NlogN）时间，O（1）空间，但比完全排序数组更高效，因为许多分区将被跳过。

您可以在此文章中找到四种方法的源代码（虽然是C#），以及它们的性能比较：查找数组的众数

1
基于你的代码，你需要改变的只有这些。
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;
}

这是您需要更改的内容。
if (repeatCount>prevRepCnt) { // a higher count of repeats than before
  • 去掉等号，就可以了。
1
我会声明另一个变量来跟踪“较低的值”。并在输入[i]值与计数相同时检查它是否小于lowerValue变量。请注意，我将">"和"="分开为条件。
int lowerValue;
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
    int lowerValue = Integer.MAX_VALUE; // initalize it with the highest integer value - 2147483647

    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
                    lowerValue = returnVal; // set the variable lowerValue to be the lower value
                }
                else if (repeatCount == prevRepCnt) && (input[i] < lowerValue) { // if it's the same number of count, take in whichever number is lower
                    returnVal=input[i]; // return that element
                    lowerValue = returnVal; // set the variable lowerValue to be the lower value
                }
                prevRepCnt = repeatCount; // Keeps the highest repeat record
            }
            repeatCount=0; // resets repeat Count for next comparison
        }
    }
    return returnVal;
}
1
你在 else if 前面缺少一个结束括号。 - Jean-François Savard
0
我的方法如下，使用HashMaps。
它将通过返回最低值来处理多模数组。
 public static int getModeOf(int[] elements){

        HashMap<Integer, Integer> frequencyOfElements = new HashMap<Integer, Integer>();

        for(int i=0;i<elements.length;i++){
            // Put the key into the map if it's not present.
            // If it is present, update frequency.
            if(!frequencyOfElements.containsKey(elements[i])){
                frequencyOfElements.put(elements[i],1);
            }
            else{
                frequencyOfElements.put(elements[i],frequencyOfElements.get(elements[i])+1);
            }
        }

        ArrayList<Integer> modes = new ArrayList<Integer>();
        int frequencyOfCurrentMode = 0;

        // We assume the first entry is the mode, then compare the remaining elements
        // from there......
        for(Map.Entry<Integer, Integer> entry : frequencyOfElements.entrySet() ){
            if(entry.getValue() >= frequencyOfCurrentMode){
               modes.add(entry.getKey());
               frequencyOfCurrentMode = entry.getValue();
           }
        }

        // If we've more than one mode, place the lowest first......
        if(modes.size() > 1) Collections.sort(modes);

        return modes.get(0);
    }
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接