陣列中尺寸k的最小字典順序子序列

給定一個整數數組，找到尺寸爲k的最小詞法子序列。 EX: Array : [3,1,5,3,5,9,2] k =4 Expected Soultion : 1 3 5 2陣列中尺寸k的最小字典順序子序列

2016-03-01 v1kas

這裏是一個greedy的算法，應該工作：

Choose Next Number (lastChoosenIndex, k) { 

    minNum = Find out what is the smallest number from lastChoosenIndex to ArraySize-k 

    //Now we know this number is the best possible candidate to be the next number. 
    lastChoosenIndex = earliest possible occurance of minNum after lastChoosenIndex 

    //do the same process for k-1 
    Choose Next Number (lastChoosenIndex, k-1) 
}

上面的算法是高度複雜的。

但是我們可以pre-sort所有數組元素paired與他們的array index並且使用單個循環貪婪地執行相同的過程。由於我們使用的分類複雜性仍然是n*log(n)

來源

2016-03-01 09:09:15

這很有道理，但是沒有針對此解決方案的動態編程方法？ – v1kas

看這裏期望的序列大小'k'是固定的。而你想要lex最小的那個尺寸。我認爲任何動態編程方法都是高度複雜的，並且基本上都是在做貪婪的方法。 –

我建議你可以嘗試使用修改後的合併排序。
修改的地方是合併部分，丟棄重複值。
選擇最小的4

的複雜度爲O（N LOGN）還在想複雜能否O（N）

來源

2016-03-01 03:22:28 Chuck

此解決方案將永遠不會工作。選擇最小的四個不是意圖。選擇詞典學最小的序列就是意圖。例如：對於輸入'2 1 1 1 9 9 9'選擇'1 9 9 9'比'2 1 1 1'好。 –

陣列中尺寸k的最小字典順序子序列

回答

相關問題