确定数组中最常见的事件
假设我有一系列双打，如下所示：
Array[10] = {10, 10, 10, 3, 10, 10, 6, 10, 10, 9, 10} 我需要一个函数来确定数组中MAJORTY投票的内容，在本例中为“10”，因为它是最常出现的数字……当然还有没有多数投票的情况（它们在哪里）等于），在这种情况下，我需要抛出exception……
有什么线索吗？ 除了在数组上做一些非常讨厌的循环之外（对于每个索引，确定有多少存在具有相同值，在数组中存储计数，然后扫描计数数组中的最高数字，并且该位置的值是获胜者等…）
使用Map应该简单如下：
int mostFrequent(int... ary) { Map m = new HashMap(); for (int a : ary) { Integer freq = m.get(a); m.put(a, (freq == null) ? 1 : freq + 1); } int max = -1; int mostFrequent = -1; for (Map.Entry e : m.entrySet()) { if (e.getValue() > max) { mostFrequent = e.getKey(); max = e.getValue(); } } return mostFrequent; }
你的第一个问题是你有一个“双打数组”，因为浮点数据的相等性是有问题的（相同的数值可以用不同的位模式表示，等等）。 如果您的双打事实上（如示例中）整数，则使用int代替。 除此之外，请仔细思考如何定义哪些值相等以表示相同的投票。
至于确定多数投票，使用带有“投票ID”作为关键字的Map和投票数作为值 – 然后最后遍历地图以找到最大值。
首先对数组进行快速排序，然后扫描并计算多数 – O（n ln n）。 如果提前知道元素的范围，例如在{1，k}之间，则可以使用将在O（n + k）中运行的计数排序。
稍微改进一下，当你扫描已排序的数组时，如果你发现有超过n / 2次出现的值就完成了。
对于一系列双打，这可能并不容易，因为对双打的平等比较是非常有问题的。 如果您可以使用整数，则可以执行以下操作：
HashMap map = new HashMap(); for(int element: Array) { Integer frequency = map.get(element); map.put(element, (frequency != null) ? frequency + 1 : 1); } int mostFrequentItem = 0; int[] maxFrequencies = new int[2]; maxFrequencies[0] = Integer.MIN_VALUE; for(Entry entry: map.entrySet()) { if(entry.getValue()>= maxFrequencies[0]) { mostFrequentItem = entry.getKey(); maxFrequencies[1] = maxFrequencies[0]; maxFrequencies[0] = entry.getValue(); } } if(maxFrequencies[1] == maxFrequencies[0]) throw new Exception();//insert whatever exception seems appropriate return mostFrequentItem
这将具有O（n）性能，因此它在渐近性能行为中应该是非常优化的。 如果您的双打不是计算结果而是来自其他来源，那么如果您可以确定基本相同的值将被平等地表示，那么您可能会使用相同的方法来获得双打，但是我会仍然建议小心这是真的。
编辑：评论中建议的一些性能改进以及支持检查不明确的情况
正如@Grizzly指出的那样，从计算的角度看，双打是有问题的。 我还建议从问题域的角度来看它们没有意义; 多数投票双打没有任何意义！
因此，假设10和6等等是人们投票的事物的整数标识符。 让我们假设您知道用户可以投票从0到10任何值。
int[] votes = ... int[] voteCounts = new int[11]; // 11 could be calculated ... for (int vote : votes) { voteCounts[vote]++; } int majority = (votes.length + 1) / 2; for (int i = 0; i < voteCounts.length; i++) { if (voteCounts[i] >= majority) { return i; // the winner! } } throw new NoClearMajorityException(...);
该算法在时间上是O(N) ，在空间中是O(M) ，其中M是最大的标识符。 问题是如果标识符是整数，它只能起作用（如所写）。
我刚用新的Java 8创建了这么漂亮的小解决方案：
import java.util.Arrays; import java.util.Collection; import java.util.HashMap; import java.util.Map; public class MostCommonObject { public static void main(String[] args) { System.out.println(mostCommonObject(new Integer[] { -4, 1, -2, 3, 1, -2, 3, 1 })); } public static T mostCommonObject(T[] array) { return mostCommonObject(Arrays.asList(array)); } public static T mostCommonObject(Collection collection) { Map map = new HashMap<>(); collection.forEach(t -> map.compute(t, (k, i) -> i == null ? 1 : i + 1)); return map.entrySet().stream().max((e1, e2) -> Integer.compare(e1.getValue(), e2.getValue())).get().getKey(); } }
试试这个，
Integer[] array=new Integer[]{10, 10, 10, 3, 10, 10, 6, 10, 10, 9, 10}; List demoList=new ArrayList (Arrays.asList(array)); Set set=new HashSet (demoList); Map myMap=new HashMap(); for (Integer integer : set) { int count=Collections.frequency(demoList, integer); myMap.put(count, integer); } int maxOccurance=myMap.get(Collections.max(myMap.keySet()));
您可以这样做：将您的数组转换为列表并对其进行排序。 选择第一个索引，并对值调用lastIndexOf（obj）。 对您遇到的每个新值执行此操作，计算值的范围并将最大范围的结果存储在变量中。
你真正想做的是计算给定集合中某些项目的出现次数。 事实上，这是在不到一天前提出的，你可能想看看这个非常相关的问题 。