如何提高演算法的時間復雜度以找到陣列中整數的最長連續子序列

有多種方法可以解決 codeforces 問題F. 連續子序列：

給你一個長度為 ?? 的整數陣列

您必須選擇這個最大長度陣列的一些子序列，以便這個子序列形成一個遞增的連續整數序列。換句話說，對于某個值 ?? 和長度 ??，所需的序列應該等于 [??,?? 1,...,?? ???1]。

可以通過從陣列中擦除一些（可能為零）元素來獲得陣列的子序列。您可以擦除任何元素，不一定要連續進行。其余元素保持其順序。例如，對于陣列 [5,3,1,2,4]，以下陣列是子序列：[3]、[5,3,1,2,4]、[5,1,4]，但陣列[1,3] 不是。

我嘗試的一種不使用動態編程的方法的 Python 代碼如下所示。為避免重復，if 陳述句會檢查陣列中是否存在比當前數字低 1 的數字，因為這樣可以包含它以增加子序列的長度。

A = [3, 3, 4, 7, 5, 6, 8]

def longestConsecutive(nums):
    longest_streak = 0 #length of longest consecutive subsequence of integers
    indices = []
    
    for i in range(1,len(nums)):
        b = set(nums[0:i]) 
        if nums[i-1] - 1 not in b:
            indices.append(i) 
            current_num = nums[i-1]
            current_streak = 1
            k = i

            for j in range(k, len(nums)):  
                if A[j] == current_num   1:
                    indices.append(j 1) 
                    current_num  = 1
                    current_streak  = 1
                    k=j   

            if current_streak < longest_streak:
                indices = indices[0:len(indices)-current_streak]  #remove the current_streak's indices 
            else: 
                longest_streak = current_streak  
    
    return [longest_streak,indices[len(indices)-longest_streak:len(indices)]] 

c = longestConsecutive(A) 
print(c[0]) 
print(*c[1])

我認為該演算法的時間復雜度為 O(n)，因為第二個 for 回圈最多運行 n 次，而第一個 for 回圈運行 n-1 次，并且每次查找都是 O(1)，因為使用了集合 b。這在 LeetCode的解決方案中解釋了一個不同但相關的問題，因為我的代碼是對所討論的第三個演算法的修改。所有其他計算都需要恒定時間。盡管如此，該演算法通過了測驗 1-4 但未通過測驗 5，其中輸入陣列的大小為 200000，并且超過了 2 秒的時間限制。問題是復雜性實際上更大嗎？有誰看到如何優化代碼？

uj5u.com熱心網友回復：

您的演算法具有 O(??2) 時間復雜度。

集合的創建已經花費了 O(1) O(2) ... O(??) = O(??2) 時間。盡管您可以通過將新值添加到現有集合來避免這種情況（而不是從頭開始重建它），但內部回圈仍然會使時間復雜度成為二次方，而這不能通過簡單的演算法調整來解決。此外，發生的切片indices[0:len(indices)-current_streak]也會損害時間復雜度。

我看不到調整該演算法以提高其時間復雜度的方法，我認為需要一種完全不同的方法。

另一種方法

具有 O(??) 時間復雜度的一種可能的解決方案——如果我們假設字典操作的攤銷時間復雜度是 O(1)——是一種跟蹤序列在字典中的結束位置并存盤對于這樣的端點，在此結束的序列的大小。

因此，例如，如果到目前為止我們已經確定了一個從 5 開始到 8 結束的序列，那么它將在該字典中用 表示{ 8: 3 }。

然后，當從輸入串列中讀取下一個值時，當它還不是該字典中的鍵時，我們可以檢查它是否在高端擴展了一個序列。然后更新字典以表示新情況是微不足道的。

當所有值都被這樣處理后，剩下的就是使用那個字典來識別最長的序列。

這個想法的 Python 實作可以在這個劇透中找到：

def longestConsecutive(nums): if not nums: # Boundary case: empty list return 0, [] size_for_end = {} for value in nums: if value not in size_for_end: if value - 1 in size_for_end: # This value extends a sequence size_for_end[value] = size_for_end.pop(value - 1) 1 else: # This is a new sequence with just one value size_for_end[value] = 1 # All sequences have been identified, so get the longest size, end = max((size, end) for end, size in size_for_end.items()) return size, list(range(end - size 1, end 1))

注意：相關的 LeetCode 問題可以通過使用兩個字典而不是一個來解決，其中第二個字典參考相同的序列，但是從該序列的起始值的角度來看，因此每個序列都由兩個字典中的條目表示.

uj5u.com熱心網友回復：

我覺得遞回函式更容易理解和遵循。基本上，您只想檢查您當前的步驟是否比以前更好，如果沒有，請繼續前進。我相信排序的部分也可以更快，因為顯然沒有必要完全排序來得出結論我們有一個非連續序列。我把它留給你改進：

def f(x,n=1):
    if len(x)<n:
        return
    elif x[:n]==sorted(x[:n]):
        a = f(x,n 1) 
        return x[:n] if a is None else a
    return f(x[1:],n)

uj5u.com熱心網友回復：

在這里，問題是找到一個有效的演算法。

建議創建一個索引陣列 ( 0 2 3 ... n-1)，并根據 的值對它們進行排序A[index]。

排序必須穩定，才能正確管理重復項。例如，只有第一個副本值得保留。

在對排序索引進行迭代時，如果有一次我們發現一個索引較低但值較高的元素，則必須在第一步中忽略該元素。但是，它的值必須被記住，以便以后再回來。

復雜性由排序決定，即O(nlogn)。

這是一個 C 代碼來說明該演算法。
輸出的索引是零索引的（C 風格）。只需添加 1 即可獲得 1 索引索引。

輸出：

1 3 5 2 4 6         -> 2  [0 3]         -> values: 1 2 
10 9 8 7            -> 1  [3]           -> values: 7 
6 7 8 3 4 5 9 10 11 -> 6  [0 1 2 6 7 8] -> values: 6 7 8 9 10 11 
5 2 3 6 7 4 8 0 9   -> 5  [0 3 4 6 8]   -> values: 5 6 7 8 9

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>

void print (const std::vector<int> &A, const std::string &after = "\n", const std::string &before = "") {
    std::cout << before;
    int n = A.size();
    for (int i = 0; i < n;   i) {
        std::cout << A[i];
        if (i != n-1) std::cout << " ";
    }
    std::cout << after;
}

std::vector<int> long_subseq (std::vector<int>& A) {
    std::vector<int> seq, seq_opt;
    int n = A.size();
    if (n == 0) return seq_opt;
    if (n == 1) {
        return std::vector<int> (1, 0);
    }
    std::vector<int> indices(n);
    std::iota (indices.begin(), indices.end(), 0);
    auto fsort = [&] (int i, int j) {return A[i] < A[j];};
    std::stable_sort (indices.begin(), indices.end(), fsort);
        
    seq.push_back (indices[0]);
    seq_opt.push_back (indices[0]);
    int max_length = 1;
    int length = 1;
    int last_index = indices[0];
    int next_index = -1;
    
    for (int i = 1; i < n;   i) {
        //std::cout << "i = " << i << "\n";
        if (A[indices[i]] == A[last_index]) continue;     
        if ((last_index < indices[i]) && (A[indices[i]] == A[last_index]   1)) {
            length  ;
            seq.push_back (indices[i]);
            last_index = indices[i];
        } else {
            if (indices[i] < last_index) {
                if (next_index == -1) next_index = i;
            }
            if (A[indices[i]] > A[last_index]   1) {             
                if (length > max_length) {
                    max_length = length;
                    std::swap (seq_opt, seq);
                }
                length = 1;
                seq.resize(0);
                if (next_index != -1) {
                    last_index = indices[next_index];
                    i = next_index - 1;
                    next_index =  -1;
                } else {
                    last_index = indices[i];
                }
                seq.push_back (last_index);
            } 
        }
    }
    if (length > max_length) {
        max_length = length;
        std::swap (seq_opt, seq);
    }
    return seq_opt;
}

int main() {
    std::vector<std::vector<int>> examples = {
        {1, 3, 5, 2, 4, 6},
        {10, 9, 8, 7},
        {6, 7, 8, 3, 4, 5, 9, 10, 11},
        {5, 2, 3, 6, 7, 4, 8, 0, 9}
    };
    
    for (auto &A: examples) {
        
        auto ans = long_subseq (A);
        print (A, " -> ");
        std::cout << ans.size() << "  ";
        print (ans, "] -> values: ", "[");
        for (int i = 0; i < ans.size();   i) {
            std::cout << A[ans[i]] << " ";
        }
        std::cout << "\n";
    }
    return 0;
}

標籤：

上一篇：將核堿基表示從ASCII轉換為UCSC.2bit

下一篇：減少陣列中不同元素的數量