/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
class Pair {
int number;
int index;
Pair(int number, int index) {
this.number = number;
this.index = index;
}
// getters and setters
public int getNumber() {
return number;
}
public int getIndex() {
return index;
}
// hashcode and equals method overriden
}
{
/*Given k sorted arrays of size n each, merge them into one sorted array.
Example: given a1 = [1, 6, 8, 9] and a2 = [3, 4, 7, 13], result should be [1, 3, 4, 6, 7, 8, 9, 13].
*/
List<integer> a1 = new List<Integer>();
a1.add (1, 6, 8, 9);
List<integer> a2 = new List<Integer>();
a2.add(3, 4, 7, 13);
List<List<Integer>> arrays = new List<List<Integer>>();
arrays.Add(a1);
arrays.Add(a2);
List<Integer> result = mergeKSortedArrays(arrays);
//O(nk log(nk))
}
public List<Integer> mergeKSortedArrays(List<List<Integer>> arrays) {
List<Integer> result = new ArrayList<Integer>();
if(arrays == null || arrays.size() == 0) {
return result;
}
int k = arrays.size();
if(arrays.get(0).size() == 0) {
return result;
}
int arraySize = arrays.get(0).size();
PriorityQueue
<Pair
<Integer, Integer
>> minHeap
= new PriorityQueue
<Integer
>(k,
new Comparator
<Pair
>() { @Override
public int compare(Pair a, Pair b) {
return a.getNumber < b.getNumber;
}); // first Integer => number, second Integer => index of the array
Iterator<Integer> iter[k];
for(int i = 0; i < k; i++) {
iter[i] = arrays.get(i).iterator();
// unit test to test each iter object is pointing to Non-Null for the arrays of size >0
Pair p = new Pair(arrays.get(i).get(0), i);
minHeap.insert(p);
}
int iterCount = 0;
while(iterCount < (arraySize * k)) {
Pair p = minHeap.extractMin();
// unit test to check if the extractMin is returning the appropriate element as the min element.
minHeap.deleteMin();
int num = p.getNumber();
result.add(num);
int index = p.getIndex();
if(iter[index].hasNext()) {
Pair newP = new Pair(iter[index].next(), index);
minHeap.insert(newP);
}
iterCount++;
}
return result;
}
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCQoJCmNsYXNzIFBhaXIgewogICAgaW50IG51bWJlcjsKICAgIGludCBpbmRleDsKICAgIAogICAgUGFpcihpbnQgbnVtYmVyLCBpbnQgaW5kZXgpIHsKICAgICAgICB0aGlzLm51bWJlciA9IG51bWJlcjsKICAgICAgICB0aGlzLmluZGV4ID0gaW5kZXg7CiAgICB9CiAgICAKICAgIC8vIGdldHRlcnMgYW5kIHNldHRlcnMKICAgIAogICAgcHVibGljIGludCBnZXROdW1iZXIoKSB7CiAgICAgICAgcmV0dXJuIG51bWJlcjsKICAgIH0KICAgIAogICAgcHVibGljIGludCBnZXRJbmRleCgpIHsKICAgICAgICByZXR1cm4gaW5kZXg7CiAgICB9CiAgICAKICAgIC8vIGhhc2hjb2RlIGFuZCBlcXVhbHMgbWV0aG9kIG92ZXJyaWRlbgp9CglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbiAoU3RyaW5nW10gYXJncykgdGhyb3dzIGphdmEubGFuZy5FeGNlcHRpb24KCXsKLypHaXZlbiBrIHNvcnRlZCBhcnJheXMgb2Ygc2l6ZSBuIGVhY2gsIG1lcmdlIHRoZW0gaW50byBvbmUgc29ydGVkIGFycmF5LiAKCkV4YW1wbGU6IGdpdmVuIGExID0gWzEsIDYsIDgsIDldIGFuZCBhMiA9IFszLCA0LCA3LCAxM10sIHJlc3VsdCBzaG91bGQgYmUgWzEsIDMsIDQsIDYsIDcsIDgsIDksIDEzXS4KKi8KTGlzdDxpbnRlZ2VyPiBhMSA9IG5ldyBMaXN0PEludGVnZXI+KCk7IAphMS5hZGQJKDEsIDYsIDgsIDkpOwpMaXN0PGludGVnZXI+IGEyID0gbmV3IExpc3Q8SW50ZWdlcj4oKTsgCmEyLmFkZCgzLCA0LCA3LCAxMyk7CgoKTGlzdDxMaXN0PEludGVnZXI+PiBhcnJheXMgPSBuZXcgTGlzdDxMaXN0PEludGVnZXI+PigpOwphcnJheXMuQWRkKGExKTsKYXJyYXlzLkFkZChhMik7Ckxpc3Q8SW50ZWdlcj4gcmVzdWx0ID0gbWVyZ2VLU29ydGVkQXJyYXlzKGFycmF5cyk7ClN5c3RlbS5vdXQucHJpbnRsbihyZXN1bHQpOwoKLy9PKG5rIGxvZyhuaykpCgp9CnB1YmxpYyBMaXN0PEludGVnZXI+IG1lcmdlS1NvcnRlZEFycmF5cyhMaXN0PExpc3Q8SW50ZWdlcj4+IGFycmF5cykgewogICAgTGlzdDxJbnRlZ2VyPiByZXN1bHQgPSBuZXcgQXJyYXlMaXN0PEludGVnZXI+KCk7CiAgICAKICAgIGlmKGFycmF5cyA9PSBudWxsIHx8IGFycmF5cy5zaXplKCkgPT0gMCkgewogICAgICAgIHJldHVybiByZXN1bHQ7CiAgICB9CiAgICAKICAgIGludCBrID0gYXJyYXlzLnNpemUoKTsKICAgIAogICAgaWYoYXJyYXlzLmdldCgwKS5zaXplKCkgPT0gMCkgewogICAgICAgIHJldHVybiByZXN1bHQ7CiAgICB9CiAgICAKICAgIGludCBhcnJheVNpemUgPSBhcnJheXMuZ2V0KDApLnNpemUoKTsKICAgIAogICAgUHJpb3JpdHlRdWV1ZTxQYWlyPEludGVnZXIsIEludGVnZXI+PiBtaW5IZWFwID0gbmV3IFByaW9yaXR5UXVldWU8SW50ZWdlcj4oaywgbmV3IENvbXBhcmF0b3I8UGFpcj4oKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgQE92ZXJyaWRlCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcHVibGljIGludCBjb21wYXJlKFBhaXIgYSwgUGFpciBiKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gYS5nZXROdW1iZXIgPCBiLmdldE51bWJlcjsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB9KTsgLy8gZmlyc3QgSW50ZWdlciA9PiBudW1iZXIsIHNlY29uZCBJbnRlZ2VyID0+IGluZGV4IG9mIHRoZSBhcnJheQogICAgCiAgICBJdGVyYXRvcjxJbnRlZ2VyPiBpdGVyW2tdOwogICAgCiAgICBmb3IoaW50IGkgPSAwOyBpIDwgazsgaSsrKSB7CiAgICAgICAgaXRlcltpXSA9IGFycmF5cy5nZXQoaSkuaXRlcmF0b3IoKTsKICAgICAgICAKICAgICAgICAvLyB1bml0IHRlc3QgdG8gdGVzdCBlYWNoIGl0ZXIgb2JqZWN0IGlzIHBvaW50aW5nIHRvIE5vbi1OdWxsIGZvciB0aGUgYXJyYXlzIG9mIHNpemUgPjAKICAgICAgICBQYWlyIHAgPSBuZXcgUGFpcihhcnJheXMuZ2V0KGkpLmdldCgwKSwgaSk7CiAgICAgICAgbWluSGVhcC5pbnNlcnQocCk7CiAgICB9CiAgICAKICAgIGludCBpdGVyQ291bnQgPSAwOwogICAgCiAgICB3aGlsZShpdGVyQ291bnQgPCAoYXJyYXlTaXplICogaykpIHsKICAgICAgICBQYWlyIHAgPSBtaW5IZWFwLmV4dHJhY3RNaW4oKTsKICAgICAgICAvLyB1bml0IHRlc3QgdG8gY2hlY2sgaWYgdGhlIGV4dHJhY3RNaW4gaXMgcmV0dXJuaW5nIHRoZSBhcHByb3ByaWF0ZSBlbGVtZW50IGFzIHRoZSBtaW4gZWxlbWVudC4KICAgICAgICAKICAgICAgICBtaW5IZWFwLmRlbGV0ZU1pbigpOwogICAgICAgIAogICAgICAgIGludCBudW0gPSBwLmdldE51bWJlcigpOwogICAgICAgIHJlc3VsdC5hZGQobnVtKTsKICAgICAgICAKICAgICAgICBpbnQgaW5kZXggPSBwLmdldEluZGV4KCk7CiAgICAgICAgaWYoaXRlcltpbmRleF0uaGFzTmV4dCgpKSB7CiAgICAgICAgICAgIFBhaXIgbmV3UCA9IG5ldyBQYWlyKGl0ZXJbaW5kZXhdLm5leHQoKSwgaW5kZXgpOwogICAgICAgICAgICBtaW5IZWFwLmluc2VydChuZXdQKTsKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgaXRlckNvdW50Kys7CiAgICB9CiAgICAKICAgIHJldHVybiByZXN1bHQ7Cn0KICAgIAp9CiAgICAKICAgIAoJCn0=
Main.java:73: error: illegal start of type
}); // first Integer => number, second Integer => index of the array
^
Main.java:75: error: ']' expected
Iterator<Integer> iter[k];
^
Main.java:75: error: illegal start of type
Iterator<Integer> iter[k];
^
Main.java:75: error: <identifier> expected
Iterator<Integer> iter[k];
^
Main.java:75: error: ';' expected
Iterator<Integer> iter[k];
^
Main.java:77: error: illegal start of type
for(int i = 0; i < k; i++) {
^
Main.java:77: error: <identifier> expected
for(int i = 0; i < k; i++) {
^
Main.java:77: error: ';' expected
for(int i = 0; i < k; i++) {
^
Main.java:77: error: illegal start of type
for(int i = 0; i < k; i++) {
^
Main.java:77: error: <identifier> expected
for(int i = 0; i < k; i++) {
^
Main.java:77: error: > expected
for(int i = 0; i < k; i++) {
^
Main.java:77: error: ';' expected
for(int i = 0; i < k; i++) {
^
Main.java:77: error: illegal start of type
for(int i = 0; i < k; i++) {
^
Main.java:77: error: <identifier> expected
for(int i = 0; i < k; i++) {
^
Main.java:77: error: ';' expected
for(int i = 0; i < k; i++) {
^
Main.java:78: error: ']' expected
iter[i] = arrays.get(i).iterator();
^
Main.java:78: error: ';' expected
iter[i] = arrays.get(i).iterator();
^
Main.java:78: error: <identifier> expected
iter[i] = arrays.get(i).iterator();
^
Main.java:78: error: <identifier> expected
iter[i] = arrays.get(i).iterator();
^
Main.java:78: error: ';' expected
iter[i] = arrays.get(i).iterator();
^
Main.java:82: error: <identifier> expected
minHeap.insert(p);
^
Main.java:82: error: <identifier> expected
minHeap.insert(p);
^
Main.java:83: error: ')' expected
}
^
Main.java:112: error: class, interface, or enum expected
}
^
24 errors