有没有一种方法可以扫描 SVD 的一维数组，这样你就可以拥有 O(n) 的复杂度？

Question

我正在尝试扫描一维数组以进行奇异值分解 (SVD) 和最坏时间，并且 space 复杂度为 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

有没有一种方法可以扫描 SVD 的一维数组，这样你就可以拥有 O(n) 的复杂度？

Is there a way to scan an one-dimension array for an SVD so you can have complexity of O(n)?

java

arrays

time-complexity

svd

space-complexity