阵列中尺寸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的最小字典顺序子序列

回答

相关问题