Наименьшая лексикографическая подпоследовательность размера k в массиве

Question

Учитывая массив целых чисел, найдите наименьшую лексическую подпоследовательность с размером k. EX: Array : [3,1,5,3,5,9,2] k =4 Expected Soultion : 1 3 5 2

Answer 1

Вот является 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 2

1. Предлагаю вам попробовать использовать модифицированную сортировку слияния. Место для
2. изменено является частью слияния, отбросить дублирующее значение.
3. выбрать наименьшее четыре

Сложность O (N LOGN) Продолжая думать, может ли сложность быть O (N)