Java Max Heap Approach


  • 0
    Y
    public class Solution {
        public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            PriorityQueue<Pair> pq = new PriorityQueue<Pair>(
                new Comparator<Pair>() {
                    public int compare(Pair a, Pair b) {
                        return b.sum - a.sum;
                    }
                }
            );
            for (int i = 0; i < k && i < nums1.length; i ++) {
                for (int j = 0; j < k && j < nums2.length; j ++) {
                    int sum = nums1[i] + nums2[j];
                    if (pq.size() == k && pq.peek().sum < sum) break;
                    pq.offer(new Pair(sum, new int[] {nums1[i], nums2[j]}));
                    if (pq.size() > k) pq.poll();
                }
            }
            ArrayList<int[]> ans = new ArrayList<int[]>();
            while (!pq.isEmpty()) {
                ans.add(0, pq.poll().pair);
            }
            return ans;
        }
    }
    
    class Pair {
        int sum;
        int[] pair;
        public Pair(int s, int[] p) {
            sum = s;
            pair = p;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.