O(n^2) Java solution without heap.


  • 0
    L

    It fails the case:
    [1,7,11]
    [2,4,6]
    3
    my result is [[2,1],[4,1],[6,1]]
    and the expected is: [[1,2],[1,4],[1,6]]
    As you can see, it is just the difference of u and v set.
    Below is my code. Anyone can help me check where is wrong?

    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            List<int[]> ret = new ArrayList();
            if(nums1 == null || nums1.length==0 || nums2==null || nums2.length==0 || k==0) return ret;
            int[] smaller = nums1[0]>=nums2[0]?nums2:nums1;
            int[] larger = nums1[0]<nums2[0]?nums2:nums1;
            for(int i=0; i<smaller.length; i++){
                for(int j=0; j<larger.length; j++){
                    int p = i, q = j;
                    if(p<smaller.length-1 && q<larger.length-1 && larger[q+1]-larger[q]>smaller[p+1]-smaller[p]){
                        break;
                    }
                    int[] tmp = new int[2];
                    tmp[1] = smaller[i];
                    tmp[0] = larger[j];
                    ret.add(tmp);
                    if(ret.size() == k) return ret;
                }
            }
            return ret;
        }
    

Log in to reply
 

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