数组中最常见的值

Question

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

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

Answer 1

如果您要以恒定的次数遍历列表来执行此操作，则需要第二个数据结构。

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

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

分析

如果在开始之前您没有该集合的下限/上限，那么您不知道要分配的计数器数组。因此，您必须对数组进行初步遍历以找到边界……现在您有了一个两遍解决方案。

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

或者

如果允许更改数组，则可以将其按升序排序O(NlogN)，然后在排序后的单次遍历中找到三个最常见的元素大批。

Answer 2

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

即循环输入数组，每次看到一个值时，都会增加“计数器”数组中的适当索引。但是，还要保留 3 个“顶级”索引（已排序）。每次增加时，请根据前 3 个索引的值检查新值，考虑到您可能只是简单地重新排序“顶部”值列表这一事实。

Answer 3

可能有更好的方法可以做到这一点，但这是一种方法。我刚刚打印了模式数组，但您可以对其进行排序以查看实际出现次数最多的数字。这很简单，因为我们知道我们正在处理的数字的上限和下限，但如果您不知道这些界限，那么您需要接受 Stephen 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; i<size; i++){
        if(tempLeader!=sarray[i]) //if we changed number tempCont is 0
            tempCont=0;

        if(sarray[i]==leader){ //if the current number in the array is our leader then keep counting
            cont++;
        }
        else{ //if not, then our new number will be tempLeader and we count that one
            tempLeader=sarray[i];
            tempCont++;
            if(tempCont>cont){ //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;
}

抱歉，这是一个蹩脚的解决方案，但它按照你的要求工作，希望它有帮助