[Print K smallest elements in their original order]

This message was edited 1 time. Last update was at 07/01/2018 19:03:33

Given an array, the task is to print K smallest elements from the array but they must be in the same order as they are in given array.

Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of two lines. First line of each test case contains two Integers N and K and the second line contains N space separated elements.

Output:
For each test case, print the K smallest elements in new line.

Constraints:
1<=T<=100
1<=K<=N<=106
1<=A[i]<=105

Example:
Input:
2
5 2
5 4 2 1 2
7 5
1 2 3 4 5 6 7
Output:
2 1
1 2 3 4 5

Значи идеја прва што ми падна да направам копија од дадената низа ... да ја соритрам по растечки редослед и после да искористам binary search .. ама нешто не ми штима бидејќи ми се повторуваат исти елементи со исти индекс ... де ваша помош малце

This message was edited 1 time. Last update was at 07/01/2018 19:55:54

Perez wrote:Значи идеја прва што ми падна да направам копија од дадената низа ... да ја соритрам по растечки редослед и после да искористам binary search .. ама нешто не ми штима бидејќи ми се повторуваат исти елементи со исти индекс ... де ваша помош малце

Не сум сигурен дека ограничувањава ти се ископирани точно, и дали временскиот лимит дозволува сортирање, ама еве да ја продолжам твојава идеја. Можеби ако чуваш за секој елемент покрај неговата вредност и позицијата, можеш прво да ги подредиш по вредност (за да ги добиеш најмалите), а потоа тие (најмалите) да ги подредиш и по позиција (индекс).
Нешто вака (не тестирав, оти баш и немам време):

This message was edited 1 time. Last update was at 07/01/2018 20:04:24

Само што го пробав моето решение тука https://practice.geeksforgeeks.org/problems/print-k-smallest-elements-in-their-original-order/0 и поминува. Ако зборуваме за истиот систем.

Точно е се да а некоја друга идеја за помало време извршување ?

This message was edited 1 time. Last update was at 07/01/2018 20:39:52

Perez wrote:Точно е се да а некоја друга идеја за помало време извршување ?

Една идеја би била Counting Sort, наместо повикот што го имам до функциите за сортирање. Бидејќи броевите се до 10^5, па можеме да искористиме таков алгоритам со линеарна сложеност.
Ама нема потреба.

Фала многу

)))

Ова чудо се врши за 0.15 сек