Based on JAVA's PriorityQueue, I created a bounded PriorityQueue


  • 0
    F
    static class Pair {
            private int x;
            private int y;
    
            public Pair(int x, int y) {
                this.x = x;
                this.y = y;
            }
    
            public int getX() {
                return x;
            }
    
            public int getY() {
                return y;
            }
    
            public int getSum() {
                return x + y;
            }
        }
    
        public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            PriorityQueue<Pair> pairs = new PriorityQueue<>((o1, o2) -> o2.x + o2.y - o1.x - o1.y);
            for (int i : nums1) {
                for (int j : nums2) {
                    Pair current = new Pair(i, j);
                    if (pairs.size() == k) {
                        if (pairs.peek().getSum() > current.getSum()) {
                            pairs.poll();
                            pairs.offer(current);
                        }
                    } else {
                        pairs.offer(current);
                    }
                }
            }
            List<int[]> list = new LinkedList<>();
            for (Pair pair : pairs) {
                list.add(new int[]{pair.getX(), pair.getY()});
            }
            return list;
        }
    

Log in to reply
 

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