Ibn
BAN USERUse minHeap to store index of List element -- from which int[], a value is extracted.
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
public class Main {
static int[] sort(LinkedList<int[]> list) {
//corner case
if(list == null ) return null;
int size =0;
//calculate size of result array
for(int[] vals: list) {
size += vals.length;
}
//corner case
if(size == 0) return null;
//create result
int res[] = new int[size];
//current idx for each of list ele
int idxs[] = new int[list.size()];
//current index of res
int index = 0;
/**
* min heap that stores index of the list, from which array in the list an element is extracted
*/
PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
Integer first = (Integer) o1;
Integer second = (Integer ) o2;
/**
* compare value at current index in array of the first to value at current index in array of the second
* Substract 1 to get current index
*/
return list.get(first)[idxs[first] -1] - list.get(second)[idxs[second] -1];
}
});
for( int i=0; i < list.size(); i++) {
int[] ar = list.get(i);
if(idxs[i] < ar.length) {
idxs[i]++;
heap.add(i);
}
}
while( ! heap.isEmpty() ) {
int listTh = heap.poll();
res[index++] = list.get(listTh)[idxs[listTh] - 1];
if(idxs[listTh] < list.get(listTh).length) {
idxs[listTh]++;
heap.add(listTh);
}
}
return res;
}
public static void main(String[] args){
int a[] = { 2, 5, 8};
int b[] = {1, 5};
int c[] = {0,99, 289};
LinkedList<int[]> list = new LinkedList<>();
list.add(a);
list.add(b);
list.add(c);
System.out.println(Arrays.toString(sort(list)));
}
}
[0, 1, 2, 5, 5, 8, 99, 289]
- Ibn October 14, 2015
top down dynamic programming.
407575348 cnt: 400
- Ibn October 14, 2015