Geek Answers Handbook

With a sorted array of n elements, sort a subset of n / 2 elements in linear time

I have a sorted array of n elements. Now they give me n / 2 elements, each of which belongs to a sorted array. Elements n / 2 are randomly selected from a sorted array. How to sort these n / 2 elements in linear time?

+6
source share
2 answers

One approach involves hashing. Create a hash set containing all n / 2 elements taken from the array. If duplicates are allowed, create a hash table from the elements at your own frequencies instead. It will take O (n) time on hold.

Then iterate over the sorted array in ascending order and for each array element we check whether it is in the hash table / hash table. If so, add this element to the output array (and if duplicates are allowed, do it once per copy of the element in the set). This will take O (1) times, as expected, per array element, and therefore this step will also take O (n) time.

Therefore, the total execution time is O (n), while waiting.

Hope this helps!

+8
source

If items fit into one array, you can use another boolean array that indicates which items were selected boolean [] selected

So, going through this array and printing only the element that was marked as selected, you can get the desired effect.

Edit: by decorating the returned object, we can even sort a subset of these random values

 boolean [] selected; Object [] data;// the array of elements ReturnObject getRandom(){ int index = random(); selected[index] = true; return new ReturnObject(index,data[index]); } void printSelected(){ for(int i = 0; i < data.length; i++){ if(selected[i]){ print(data[i]); } } } void printSubset(ReturnObject[]set){ boolean []selected = .... for(int i = 0; i < set.length; i++){ selected[set[i].index] = true; } for(int i = 0; i < data.length; i++){ if(selected[i]){ print(data[i]); } } } class ReturnObject{//Class decorating the return object, which includes its index in the data array int index; Object data; }
0
source

More articles:


All Articles