Java 查找数组中整数的众数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/23946397/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding the Mode of Integers in an Array
提问by Hyman L.
For this problem, I am to write a method called mode that returns the most frequently occurring element of an array of integers. Assume that the array has at least one element and that every element in the array has a value between 0 and 100 inclusive. Break ties by choosing the lower value.
对于这个问题，我将编写一个名为 mode 的方法，该方法返回整数数组中出现频率最高的元素。假设数组至少有一个元素，并且数组中的每个元素都有一个介于 0 和 100 之间的值。通过选择较低的值打破联系。
For example, if the array passed contains the values {27, 15, 15, 11, 27}, your method should return 15. (Hint: You may wish to look at the Tally program from earlier in this chapter to get an idea of how to solve this problem.)
例如，如果传递的数组包含值 {27, 15, 15, 11, 27}，则您的方法应返回 15。（提示：您可能希望查看本章前面的 Tally 程序以了解如何解决这个问题呢。）
I am having a problem seeing what is going wrong for a specific input. For instance:
我在查看特定输入出了什么问题时遇到了问题。例如：
mode({27, 15, 15, 27, 11, 11, 11, 14, 15, 15, 16, 19, 99, 100, 0, 27}) returns 15 which is correct, but mode({1, 1, 2, 3, 3}) returns 3 when it should be 1.
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。
Here is the code:
这是代码：
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;
}
采纳答案by Edwin Torres D.Eng.
Here's a simpler way to solve this problem. Create an array called count of size 101. The indexes (0-100) represent the numbers you are counting. Traverse the input array and count the occurrences of each number. Finally, compare the counts to find the one that appears the most (tie goes to the lower number):
这里有一个更简单的方法来解决这个问题。创建一个大小为 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;
}
回答by Sky
I would declare another variable to keep track of the "lower value". And check if the input[i] value is smaller than the lowerValue variable when it has the same count. Note I separated the > & = for your condition.
我会声明另一个变量来跟踪“较低的值”。并检查 input[i] 值是否小于 lowerValue 变量，当它具有相同的计数时。请注意，我将 > & = 分隔为您的条件。
int lowerValue;
int 低值；
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;
}
回答by Zoran Horvat
I have recently analyzed four ways to calculate mode of the array:
我最近分析了四种计算数组众数的方法：
- If range of numbers in the array is small then use counting sort - O(N) time, (N) space but very efficient. This solution is directly applicable to the problem you are asking about, since you have only 101 possible values in the array.
- Index elements in the array in hash table - O(N) time, O(N) space. This solution is applicable if values are taken from a large range, such as all integer numbers.
- Sort the array and then count successive equal elements - O(NlogN) time, O(1) space. This solution is applicable if array is too large to build an index.
- Partially sort the array but skip partitions smaller than current candidate - O(NlogN) time, O(1) space but much more efficient than fully sorting the array because many partitions will be skipped.
- 如果数组中的数字范围很小，则使用计数排序 - O(N) 时间，(N) 空间但非常有效。此解决方案直接适用于您所询问的问题，因为数组中只有 101 个可能的值。
- 哈希表中数组中的索引元素 - O(N) 时间，O(N) 空间。如果值取自大范围（例如所有整数），则此解决方案适用。
- 对数组进行排序，然后计算连续的相等元素 - O(NlogN) 时间，O(1) 空间。如果数组太大而无法构建索引，则此解决方案适用。
- 部分排序数组但跳过小于当前候选的分区 - O(NlogN) 时间，O(1) 空间但比完全排序数组更有效，因为将跳过许多分区。
You can find source code (although in C#) for all four methods and performance comparison in this article: Finding Mode of an Array
您可以在本文中找到所有四种方法和性能比较的源代码（尽管是 C#）：Finding Mode of an Array
回答by Edwin H.
Base on your code all you need to change is.
根据您的代码，您需要更改的只是。
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;
}
here is what you need to change.
这是您需要更改的内容。
if (repeatCount>prevRepCnt) { // a higher count of repeats than before
- take out the equal sign and you should be good.
- 取出等号，你应该很好。
回答by DylanR
My approach is below using HashMaps.
我的方法如下使用 HashMaps。
It will deal with multi-modal arrays by returning the lowest value.
它将通过返回最低值来处理多模式数组。
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);
}
