在陣列x,y中找到兩個數字，其中x<y，x至少重復n/3次，y至少重復n/4次-有解無憂

我一直在努力解決線性時間的陣列問題，問題是：假設我們有一個陣列 A [1...n] 撰寫一個回傳 true 的演算法，如果：陣列 x,y 中有兩個數字有以下幾點：

x < y
x 重復超過 n/3 次
y 重復超過 n/4 次

假設我們有一個排序陣列，我試圖撰寫以下 java 程式來這樣做，但我認為這不是最好的實作。

    public static boolean solutionManma(){
    int [] arr = {2,2,2,3,3,3};
    int n = arr.length;
    int xCount = 1;
    int yCount = 1;
    int maxXcount= xCount,maxYCount = yCount;
    int currX = arr[0];
    int currY = arr[n-1];

    for(int i = 1; i < n-2;i  ){
        int right = arr[n-2-i 1];
        int left = arr[i];

        if(currX == left){
            xCount  ;
        }
        else{
            maxXcount = Math.max(xCount,maxXcount);
            xCount = 1;
            currX = left;
        }
        if(currY == right){
            yCount  ;
        }
        else {
            maxYCount = Math.max(yCount,maxYCount);
            yCount = 1;
            currY = right;
        }

    }
    return (maxXcount > n/3 && maxYCount > n/4);
}

如果有人對這類問題有演算法想法（最好是 O(n)），我將不勝感激，因為我被這個問題困住了。

uj5u.com熱心網友回復：

這個問題的關鍵部分是在線性時間和常數空間中找到出現超過 n/4 次的值。（注意：你的問題的文字說“超過”，標題說“至少”。這些不是同一個條件。這個答案是基于你的問題的文字。）

最多有三個值出現超過 n/4 次，并且這些值的串列還必須包括出現超過 n/3 次的任何值。

我們將使用的演算法回傳一個最多包含三個值的串列。它只保證滿足條件的所有值都在它回傳的串列中。該串列可能包含其他值，并且不提供有關精確頻率的任何資訊。

所以第二遍是必要的，它第二次掃描向量，計算回傳的三個值中每一個的出現次數。一旦你有了三個計數，就很容易檢查出現超過 n/3 次（如果有的話）的最小值是否小于出現超過 n/4 次的最大值。

為了構建候選人串列，我們使用了 Boyer-Moore 多數投票演算法的推廣，該演算法找到了一個出現超過 n/2 次的值。由 J. Misra 和 D. Gries 于 1982 年發表的概括使用k-1可能與一個值相關聯的計數器來識別可能出現1/k多次的值。在這種情況下，k是 4，所以我們需要三個計數器。

最初，所有的計數器都是 0 并且不與任何值相關聯。然后對于陣列中的每個值，我們執行以下操作：

如果有一個與該值關聯的計數器，我們將其遞增。
如果沒有計數器與該值關聯，但某個計數器為 0，我們將該計數器與該值關聯并將其計數增加到 1。
否則，我們會減少每個計數器的計數。

處理完所有值后，與具有正計數的計數器關聯的值就是候選值。

對于k事先不知道的一般實作，可以使用哈希表或其他鍵值映射來識別具有計數的值。但在這種情況下，由于已知它k是一個小常數，我們可以只使用三個值計數對的簡單向量，使該演算法的時間為 O(n)，空間為 O(1)。

uj5u.com熱心網友回復：

您可以使用IntStream流式傳輸陣列，并anyMatch()檢查是否有任何值滿足所有條件：

public static boolean check(int [] arr) {
    int length = arr.length;
    
    double timesX = length / 3d;
    double timesY = length / 4d;
    
    return IntStream.of(arr).distinct()
            .anyMatch(x -> count(arr, x) > timesX && IntStream.of(arr)
                    .anyMatch(y -> x < y && count(arr, y) > timesY));
}

private static long count(int [] arr, int value) {
    return IntStream.of(arr).filter(i -> i == value).count();
}

uj5u.com熱心網友回復：

我將建議以下解決方案，使用以下假設：

在一個長度陣列中n，最多會有n不同的數字

關鍵特征是使用帶箱的直方圖計算每個不同輸入的出現頻率n，即O(n)空間。演算法如下：

創建一個帶nbin 的直方圖向量，初始化為零
ii輸入陣列長度的索引a

2.1。增加值：hist[a[ii]] =1
設定found_x和found_y_False
對于ii直方圖中的第 th 個 bin，檢查：

4.1。如果found_x == False

4.1.1。如果hist[ii] > n/3，設定 found_x = True并設定x = ii

4.2. 否則如果found_y == False

4.2.1。如果hist[ii] > n/4，設定y = ii并回傳x, y

解釋

在陣列的第一次運行中，您記錄了所有數字的出現頻率。在直方圖陣列的運行中，它的長度也為n，您檢查出現情況。首先，您檢查是否有一個數字出現了n/3多次，如果有，對于其余的數字（默認情況下大于x直方圖中的檔案），您檢查是否有另一個數字出現了n/4多次。如果有，則回傳找到的x，y如果沒有，則在覆寫直方圖中的所有 bin 后簡單地回傳 not found。

就時間復雜度而言，您只需遍歷一次輸入陣列，然后遍歷一次具有相同長度的直方圖，因此需要時間復雜度O(n)。

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/452509.html

標籤：爪哇数组算法数据结构时间复杂度

上一篇：如何優化brainf*ck指令

下一篇：當定義如下時如何生成正六邊形序列？