12ms Java priority queue solution


  • 0
    M
    public class Solution {
        public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            PriorityQueue<int[]> pq = new PriorityQueue<>(1, new Comparator<int[]>(){
                public int compare(int[] a, int[] b) {
                    return (b[0] + b[1]) - (a[0] + a[1]);
                }
                });
            for (int i = 0; i < nums1.length; i++) {
                for (int j = 0; j < nums2.length; j++) {
                    if (pq.size() < k) {
                        pq.offer(new int[]{nums1[i], nums2[j]});
                    } else {
                        if (pq.peek()[0] + pq.peek()[1] > nums1[i] + nums2[j]) {
                            pq.poll();
                            pq.offer(new int[]{nums1[i], nums2[j]});
                        } else {
                            break;
                        }
                    }
                }
            }
            List<int[]> res = new ArrayList<>(pq);
            return res;
        }
    }

Log in to reply
 

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