Java, compare the time between minPQ(n1 + n2) vs minPQ(k)


  • 0
    N

    intuitively, we can use minPQ to store all the sum from nums1 and nums2, and then output the minimum K pairs (43 ms)

    class Pair {
        int x;
        int y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
        
        public int getSum() {
            return x + y;
        }
    }
    
    public class Solution {
        
        
        public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            List<int[]> res = new ArrayList<int[]>();
            
            if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
                return res;
            }
            
            PriorityQueue<Pair> minPQ = new PriorityQueue<Pair>(nums1.length * nums2.length, new Comparator<Pair>(){
               @Override
               public int compare(Pair a, Pair b) {
                   return a.getSum() - b.getSum();
               }
            });
            
            for (int i = 0; i < nums1.length; i++) {
                for (int j = 0; j < nums2.length; j++) {
                    Pair cur = new Pair(nums1[i], nums2[j]);
                    minPQ.add(cur);
                }
            }
            
            for (int i = 0; i < k && !minPQ.isEmpty(); i++) {
                int[] arr = new int[2];
                Pair cur = minPQ.poll();
                arr[0] = cur.x;
                arr[1] = cur.y;
                res.add(arr);
            }
            return res;
        }
    }
    

    thanks to @bbccyy1 , we can use minPQ(size k) to store the information, and the running time is 8 ms

    class Pair {
        int x;
        int y;
        int index;
        
        public Pair(int x, int y, int i) {
            this.x = x;
            this.y = y;
            this.index = i;
        }
        
        public int getSum() {
            return x + y;
        }
    }
    
    public class Solution {
        public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            List<int[]> res = new ArrayList<int[]>();
            
            if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
                return res;
            }
            
            PriorityQueue<Pair> minPQ = new PriorityQueue<Pair>(k, new Comparator<Pair>(){
               @Override
               public int compare(Pair a, Pair b) {
                   return a.getSum() - b.getSum();
               }
            });
            
            for (int i = 0; i < nums1.length; i++) {
                Pair cur = new Pair(nums1[i], nums2[0], 0);
                minPQ.add(cur);
            }
            
            while (k > 0 && !minPQ.isEmpty()) {
                k--;
                Pair cur = minPQ.poll();
                res.add(new int[]{cur.x, cur.y});
                if (cur.index == nums2.length - 1) {
                    continue;
                }
                else {
                    minPQ.add(new Pair(cur.x, nums2[cur.index + 1], cur.index + 1));
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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