Java similar solutions to Intersection of Two Arrays I & II


  • 0
    W

    Intersection of Two Arrays I:
    ...

    // Simple version:
    public int[] intersection(int[] nums1, int[] nums2) {
        
        if(nums2.length > nums1.length){
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }
        
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int intersectionIndex = -1;
        int startIndex = 0;
        for(int i=0; i<nums2.length; i++){
            if(i>0 && nums2[i-1]==nums2[i]){
                continue;
            }
            int bsIndex = Arrays.binarySearch(nums1, startIndex, nums1.length, nums2[i]);
            if(bsIndex >= 0){
                startIndex = bsIndex + 1;
                nums2[++intersectionIndex] = nums2[i];
            }
        }
        
        return Arrays.copyOf(nums2, intersectionIndex+1);
    }
    
    //----------------------------------------------------------------------------
    
    // Optimized version:
    public int[] intersection(int[] nums1, int[] nums2) {
    
        if(nums1.length < nums2.length){
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }
        
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int intersectionIndex = 0;
        int startIndex = 0;
        for(int i=0; i<nums2.length; i++){
            if(i>0 && nums2[i-1]==nums2[i]){
                continue;
            }
            int bsIndex = binarySearchLastOccur(nums1, startIndex, nums1.length, nums2[i]);
            if(bsIndex >= 0){
                startIndex = bsIndex + 1;
                nums2[intersectionIndex++] = nums2[i];
            }
        }
        
        return Arrays.copyOf(nums2, intersectionIndex);
    }
    
    public int binarySearchLastOccur(int[] nums, int startIndex, int endIndex, int target){
        int lowIndex = startIndex;
        int highIndex = endIndex-1;
        while(lowIndex <= highIndex){
            int midIndex = lowIndex + (highIndex-lowIndex)/2;
            if(nums[midIndex] > target){
                highIndex = midIndex-1;
            }else if((nums[midIndex] < target) ||
                      (midIndex<highIndex && nums[midIndex+1]==target)){
                lowIndex = midIndex+1;
            }else {
                return midIndex;
            }
        }
        return -1;
    }
    

    ...

    Intersection of Two Arrays II:
    ...

    // Simple version:
    public int[] intersect(int[] nums1, int[] nums2) {
    
        if(nums1.length < nums2.length){
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }
        
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int intersectionIndex = 0;
        int startIndex = 0;
        for(int i=0; i<nums2.length; i++){
            int bsIndex = Arrays.binarySearch(nums1, startIndex, nums1.length, nums2[i]);
            if(bsIndex >= 0){
                while(bsIndex>startIndex && nums1[bsIndex-1]==nums2[i]){
                    bsIndex--;
                }
                startIndex = bsIndex + 1;
                nums2[intersectionIndex++] = nums2[i];
            }
        }
        
        return Arrays.copyOf(nums2, intersectionIndex);
    }
    
    //----------------------------------------------------------------------------
    
    // Optimized version
    public int[] intersect(int[] nums1, int[] nums2) {
    
        if(nums1.length < nums2.length){
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }
        
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int intersectionIndex = 0;
        int startIndex = 0;
        for(int i=0; i<nums2.length; i++){
            int bsIndex = binarySearch1stOccur(nums1, startIndex, nums1.length, nums2[i]);
            if(bsIndex >= 0){
                startIndex = bsIndex + 1;
                nums2[intersectionIndex++] = nums2[i];
            }
        }
        
        return Arrays.copyOf(nums2, intersectionIndex);
    }
    
    public int binarySearch1stOccur(int[] nums, int startIndex, int endIndex, int target){
        int lowIndex = startIndex;
        int highIndex = endIndex-1;
        while(lowIndex <= highIndex){
            int midIndex = lowIndex + (highIndex-lowIndex)/2;
            if(nums[midIndex] < target){
                lowIndex = midIndex+1;
            }else if((nums[midIndex] > target) ||
                      (midIndex>startIndex && nums[midIndex-1]==target)){
                highIndex = midIndex-1;
            }else {
                return midIndex;
            }
        }
        return -1;
    }
    

    ...


Log in to reply
 

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