数组中长度为k的最小字典序子序列

Question

给定一个整数数组，找到大小为k的最小字典子序列。 例如：数组：[3,1,5,3,5,9,2] k =4 期望的解决方案：1 3 5 2

- curious_cat

---

Shreyas Shetty（https://stackoverflow.com/users/11102816）发布了一个[答案](https://stackoverflow.com/a/65420286)，表示在 https://leetcode.com/problems/find-the-most-competitive-subsequence/ 上有解决方案。 - Scratte

Answer 1

问题可以通过维护一个双端队列（deque）在O(n)时间复杂度内解决。我们从左到右迭代元素，并确保deque始终保持该点上最小的字典序列。只有当当前元素比deque中的元素小且deque中的元素加上剩余要处理的元素至少为k时才应弹出元素。

vector<int> smallestLexo(vector<int> s, int k) {
    deque<int> dq;
    for(int i = 0; i < s.size(); i++) {
        while(!dq.empty() && s[i] < dq.back() && (dq.size() + (s.size() - i - 1)) >= k) {
            dq.pop_back();
        }
        dq.push_back(s[i]);
    }
    return vector<int> (dq.begin(), dq.end());
}

此函数用于寻找给定向量中字典序最小的长度为k的子序列。它使用双端队列(dq)维护一个单调递增的子序列，其中dq的大小加上未处理元素数量至少为k。在遍历输入向量时，如果当前元素小于dq中的最后一个元素，则将其从dq中弹出，直到dq为空或当前元素不再小于dq的最后一个元素或dq的大小满足要求为止。然后将当前元素插入dq中。最后返回dq的所有元素作为结果。

- Ankit Joshi

Answer 2

这里有一个应该能够工作的贪心算法：

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 )
}

上述算法复杂度较高。

但是，我们可以将所有的数组元素与它们的数组索引成对预排序，并使用单个循环贪心地执行相同的过程。 由于我们使用了排序，复杂度仍为n*log(n)

- Obaida.Opu

---

这个解决方案很有道理，但是难道没有一种动态规划的方法吗？ - curious_cat

请注意，期望的序列大小 k 是固定的。而您想要的是最小的字典序列。我认为任何动态规划方法都具有很高的复杂度，并且基本上会做与贪心方法相同的事情。 - Obaida.Opu

Answer 3

安基特·乔希的回答是可行的。但我认为只使用向量本身就可以完成，而不必使用双端队列，因为所有操作都可以在向量中完成。此外，在安基特·乔希的答案中，双端队列可能包含额外的元素，我们必须在返回之前手动弹出这些元素。在返回之前添加以下行。

最初的回答有效，但我认为只使用vector即可，不需要使用deque，因为vector中也有所有的操作。此外，在Ankit Joshi的答案中，deque可能包含额外的元素，我们必须在返回之前手动弹出这些元素。在返回之前添加以下行。

while(dq.size() > k)
{
       dq.pop_back();
}

- Chandramowli

Answer 4

可以使用O(n) + Klog(n)的RMQ完成。 使用O(n)构建RMQ。 现在找到序列，其中每个第i个元素将是pos [x(i-1)+1到n-(K-i)]中最小的数字（对于i [1到K]，其中x0 = 0，xi是给定数组中第i个最小元素的位置）。

- ANKIT KUMAR

Answer 5

如果我理解问题正确的话，这里有一个DP算法，应该可以工作，但它需要O(NK)时间。

//k is the given size and n is the size of the array
create an array dp[k+1][n+1]

initialize the first column with the maximum integer value (we'll need it later)
and the first row with 0's (keep element dp[0][0] = 0)

now run the loop while building the solution 

for(int i=1; i<=k; i++) {
  for(int j=1; j<=n; j++) {
      //if the number of elements in the array is less than the size required (K) 
      //initialize it with the maximum integer value
      if( j < i ) {
          dp[i][j] = MAX_INT_VALUE;
      }else {
          //last minimum of size k-1 with present element or last minimum of size k
          dp[i][j] = minimun (dp[i-1][j-1] + arr[j-1], dp[i][j-1]);
      } 
   }
}
//it consists the solution
return dp[k][n];

数组的最后一个元素包含了解决方案。

- Lakshya

Answer 6

1. 我建议您可以尝试使用修改后的归并排序。修改的地方在于合并部分，舍弃重复值。
2. 选择最小的四个。
3. 时间复杂度为O(n logn)。仍在思考是否可以将复杂度降至O(n)。

- Chuck

---

这个解决方案永远不会奏效。选择最小的四个数并不是意图，选择字典序最小的序列才是意图。 例如：对于输入 2 1 1 1 9 9 9，选择 1 9 9 9 比选择 2 1 1 1 更好。 - Obaida.Opu