Get smallest t items from an array of integers of size n

Asked Feb 03 '17 at 20:58

Active Feb 03 '17 at 21:19

Viewed 60 times

I have an array of size n of unsorted integers and I would like to print the smallest t elements from it.

For example, if I have the following array:

int[] input = {5,6,2,5,7,8,9,1,22,64,3,4} 
int t = 5;

Then my result should be:

result = {1,2,3,4,5}

Requested code:

Arrays.sort(input);

for(int i = 0; i <= t; i++) {
    System.out.println(input[i]);
}

Currently how I'm going it is I'm sorting the array using Arrays.sort(), and then iterating through the first t terms to print it. This solves the problem in O(nlgn). However, if I have a an array with a sufficiently large size (n > 1000) then it seems like bad practice to sort the whole thing to get t number of elements (assuming t is much smaller than n).

I was wondering if there is some other data structure in Java which can do it more efficiently? Maybe something that linearly probes the array and creates a smaller array of size t and fills it with the smallest t elements in the original array by utilizing some check?

I was looking into a Priority Queue or a MinHeap but I'm not sure if it solves the problem I'm having, which is to solve it in better than O(nlgn) time.

Do you guys have any ideas?

edited Feb 03 '17 at 21:19

asked Feb 03 '17 at 20:58

FlameDra

1,807
7
30
47

Just use a ring buffer. – Boris the Spider Feb 03 '17 at 20:59
Do my home work for me question? – Norbert Feb 03 '17 at 21:00
where is your code ? – Mohsen_Fatemi Feb 03 '17 at 21:02
send it , i'll help you – Mohsen_Fatemi Feb 03 '17 at 21:02
Does the output have to be sorted? – David Eisenstat Feb 03 '17 at 21:07
2

I think you should investigate the min heap idea further. If I remember correctly, building a min heap is O(n). Subsequently, as you remove each minimum element, maintaining the min heap is O(log n). So you have `t` times log(n) accesses plus O(n), which is less than O(n log n). – David Choweller Feb 03 '17 at 21:13
@Mohsen_Fatemi I added in my code. Since its so straightforward I thought people would be able to get it without me pasting it in. – FlameDra Feb 03 '17 at 21:20
@DavidEisenstat It can be sorted in O(tlgt) time which is better than O(nlgn) so its still better. – FlameDra Feb 03 '17 at 21:21
@FlameDra people are able to get it , some people send their homework and try to get the code that they can't write it ... – Mohsen_Fatemi Feb 03 '17 at 21:53
this is not the true code , wrong answer for that input ... – Mohsen_Fatemi Feb 03 '17 at 21:54
maybe it was better to use Map ... – Mohsen_Fatemi Feb 03 '17 at 21:55

Get smallest t items from an array of integers of size n

0 Answers0