My code:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
public class Solution {
private class entry {
int[] key;
int val;
entry(int[] key, int val) {
this.key = key;
this.val = val;
}
}
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> ret = new ArrayList<int[]>();
if (nums1 == null || nums2 == null || k <= 0) {
return ret;
}
PriorityQueue<entry> pq = new PriorityQueue<entry>(k, new Comparator<entry>() {
public int compare(entry e1, entry e2) {
return -1 * (e1.val - e2.val);
}
});
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
int[] key = new int[2];
key[0] = nums1[i];
key[1] = nums2[j];
pq.offer(new entry(key, key[0] + key[1]));
if (pq.size() > k) {
pq.poll();
}
}
}
while (!pq.isEmpty()) {
ret.add(pq.poll().key);
}
Collections.sort(ret, new Comparator<int[]> () {
public int compare(int[] o1, int[] o2) {
return o1[0] + o1[1] - o2[0] - o2[1];
}
});
return ret;
}
}
其实和 top k frequent number 差不多的思路。
也是建一个priority queue存 map, value 作为优先级比较，key作为我们最后需要的输出。
Anyway, Good luck, Richardo! -- 09/15/2016
