有没有办法扫描SVD的一维数组，因此你可以有O（n）的复杂性？

Question

我试图扫描一维数组的奇异值分解（SVD）和最差的时间和空间复杂度为O（n）而不使用任何二级数据结构。

他们设法做到的唯一方法是使用嵌套循环，但这样做就是O（n ^ 2）

public static void svd(Integer[] array){
    int count = 0;
    int svd = 0;

    for (int i = 0; i < array.length; i++) {
        count=0;
        for (int j = 0; j < array.length; j++) {
            if(array[i] == array[j]){
                count++;

        }
        if(count>(array.length/2)){
            svd = array[i];
            System.out.println("svd = "+svd);
        }
        else if(count<array.length/2){}
        }
    }
} 

Answer 1

答案是使用Boyer-Moore多数投票算法

https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm