数组中最常见的值

我如何找到arrays中三个最常见的元素？ 我正在使用长度为10,000的数组，其中元素= 0-100的随机整数。

我正在考虑使用两个数组，一个长度为100，只是使用if语句递增。 但是，我想知道是否有一种方法只能使用一个for / if循环（语句）来查找这些值。

Answer 1

如果要在列表中的常数传递中执行此操作，则需要第二个数据结构。

如果您具有该集合中的值的下限和上限，并且值相对密集，则计数器数组是一个很好的解决方案。

否则，最好使用Map ，其中键是集合的元素，值是计数器。

分析

如果在开始之前没有设置上限/上限，那么你不知道要分配的大数量的计数器。 所以你必须对数组进行初步传递才能找到界限……现在你有了一个两遍解决方案。

如果你确实有下限和上限但是集合很稀疏，那么初始化计数数组的成本+找到三个最大计数的成本将主导计算集合元素的成本。 如果差异足够大（即输入很大且非常稀疏），HashMap将更快并且将占用更少的内存。

另外

如果允许更改数组，可以按升序O(NlogN)对其进行排序，然后在排序数组的单次传递中找到三个最常见的元素。

Answer 2

你可以在一个循环中完成它，但我认为你仍然需要第二个数组。

即循环输入数组，每次看到一个值时，都会在“计数器”数组中增加相应的索引。 但是，还要保留3个“顶级”索引（已排序）。 每次递增时，请根据前3个索引中的值检查新值，以确定您可能正在处理只是重新排序“顶部”值列表的事实。

Answer 3

可能有更好的方法来做到这一点，但这是一种方式。 我刚刚打印了模式数组，但您可以对其进行排序以查看实际发生的数量最多。 这很简单，因为我们知道我们正在弄乱的数字的上限和下限，但是如果你不知道那些界限那么你需要接受斯蒂芬C给出的建议。

 public class Main { public static void main(String[] args) { int i; int value; //one greater than max value because Math.random always returns a value less than 1.0 //this number also works good for our mode array size int maxValue = 101; int[] originalArray = new int[10000]; int[] modeArray = new int[maxValue]; for(i = 0; i < originalArray.length; i++){ value = (int) (Math.random() * maxValue); originalArray[i] = value; } for(i = 0; i < originalArray.length; i++){ modeArray[originalArray[i]] += 1; } for(i = 0; i < modeArray.length; i++){ System.out.println("Number " + i + " occurred " + modeArray[i] + " times"); } } } 

Answer 4

  //find majority of a value in a array — O(n log n) -> wrost case O(n) void findMajority(){ //sort sort(begin(sarray),end(sarray)); //sarray[0] is our first number already counted int cont=1; int leader = sarray[0]; //temp variables to know when we changed to a different number int tempLeader=0; int tempCont=0; //loop through sarray.size() for(unsigned int i=1; icont){ //its not higher occurences than our last number? skip, else we got a new leader leader=tempLeader; cont=tempCont; tempLeader=0; tempCont=0; } } } cout << "leader is" << leader << endl; } 

抱歉，这是一个糟糕的解决方案，但它的工作方式就像你问的那样，希望它有所帮助