java PQ solution


  • 0
    S
        public class P {
            int a,b;
            public P (int a, int b) {
                this.a = a;
                this.b = b;
            }
            
            @Override
            public boolean equals(Object o) {
                if (!(o instanceof P))
                    return false;
                P p = (P)o;
                return p.a == this.a && p.b == this.b;
            }
            
            @Override
            public int hashCode() {
                return this.a << 16 + this.b;   
            }
        }
        
        public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            PriorityQueue<P> pq = new PriorityQueue<P>(new Comparator<P>() {
                public int compare (P p1, P p2) {
                    return nums1[p1.a] + nums2[p1.b] - nums1[p2.a] - nums2[p2.b];
                }    
            });
            
            List<int[]> result = new ArrayList<>(k);
            int n1 = nums1.length, n2 = nums2.length;
            
            if (n1 == 0 || n2 == 0)
                return result;
            pq.add(new P(0, 0));
            int count = 0;
            Set<P> set = new HashSet<>();
            P p, p1,p2;
            int limit = n1 * n2;
            
            while (count < k && count < limit) {
                p = pq.poll();
                count++;
                result.add(new int[] {nums1[p.a], nums2[p.b]});
                
                if (p.a + 1 < n1) {
                    p1 = new P(p.a + 1, p.b);
                    if (!set.contains(p1)) {
                        set.add(p1);
                        pq.add(p1);
                    }
                }
    
                if (p.b + 1 < n2) {
                    p2 = new P(p.a, p.b + 1);
                    if (!set.contains(p2)) {
                        set.add(p2);
                        pq.add(p2);
                    }
                }
            }
            return result;
        }
    }

Log in to reply
 

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