给定一个整数数组,找到大小为k的最小字典子序列。
例如:数组:[3,1,5,3,5,9,2] k =4
期望的解决方案:1 3 5 2
给定一个整数数组,找到大小为k的最小字典子序列。
例如:数组:[3,1,5,3,5,9,2] k =4
期望的解决方案:1 3 5 2
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的所有元素作为结果。
这里有一个应该能够工作的贪心算法:
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)
k
是固定的。而您想要的是最小的字典序列。我认为任何动态规划方法都具有很高的复杂度,并且基本上会做与贪心方法相同的事情。 - Obaida.Opu安基特·乔希的回答是可行的。但我认为只使用向量本身就可以完成,而不必使用双端队列,因为所有操作都可以在向量中完成。此外,在安基特·乔希的答案中,双端队列可能包含额外的元素,我们必须在返回之前手动弹出这些元素。在返回之前添加以下行。
最初的回答有效,但我认为只使用vector即可,不需要使用deque,因为vector中也有所有的操作。此外,在Ankit Joshi的答案中,deque可能包含额外的元素,我们必须在返回之前手动弹出这些元素。在返回之前添加以下行。
while(dq.size() > k)
{
dq.pop_back();
}
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];
2 1 1 1 9 9 9
,选择 1 9 9 9
比选择 2 1 1 1
更好。 - Obaida.Opu