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

Question

给定一个整数数组，找到大小为 k 的最小词法子序列。 EX: Array : [3,1,5,3,5,9,2] k =4 Expected Soultion : 1 3 5 2

Answer 1

我建议您可以尝试使用修改后的归并排序。
修改为合并部分，丢弃重复值。
select最小的四个

复杂度为o(n logn) 还在想复杂度能不能o(n)

Answer 2

这是一个应该有效的 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)

Answer 3

如果我没看错问题，这里有一个 DP 算法应该可以工作，但它需要 O(NK) time。

//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];

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

Answer 4

这个问题可以通过维护一个双端队列(deque)在O(n)中解决。我们从左到右迭代元素，并确保双端队列始终保持到该点为止的最小词典序列。如果当前元素小于deque中的元素，并且deque中的元素总数加上剩余待处理的元素至少为k，我们才应该弹出元素。

<code>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());
}

Answer 5

Ankit Joshi 的回答有效。但我认为它可以只用一个 vector 本身来完成，而不是使用 deque 因为所有完成的操作都可以在 vector 中使用。同样在 Ankit Joshi 的回答中，双端队列可以包含额外的元素，我们必须在返回之前手动弹出这些元素。在返回之前添加这些行。

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

Answer 6

可以用RMQ在O(n) + Klog(n)中完成。在 O(n) 中构建 RMQ。现在找到每个第 i^th 个元素将是最小编号的序列。从 pos [x_(i-1)+1 到 n-(K-i)] （对于 i [1 到 K] ，其中 x₀ = 0, x_i是给定数组中第i_个最小元素的位置)

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

Smallest Lexicographic Subsequence of size k in an Array

arrays

dynamic-programming

greedy