Java Solution Using Binary Search


  • 0
    H
    class Solution {
        public int[] intersect(int[] nums1, int[] nums2) {
            if (nums1 == null || nums1.length < 1 || nums2 == null || nums2.length < 1)
                return new int[0]; 
            
            int m = nums1.length; 
            int n = nums2.length; 
            
            //Make sure nums1 has the shortest length.
            if(m > n) {
                int[] tempArr = nums1; 
                nums1 = nums2; 
                nums2 = tempArr; 
                
                int tempLen = m; 
                m = n; 
                n = tempLen; 
            } 
            
            Arrays.sort(nums1);
            Arrays.sort(nums2);
            ArrayList<Integer> list = new ArrayList();
            
            //Loop through the shorter array, if possible
            for (int i : nums1){
                int pos = binarySearch(nums2, i, 0, nums2.length);
                
                if (pos != -1){
                    //Found it, delete it from the second array, to prevent duplicate
                    ArrayList<Integer> arrayList = convertArrayToList(nums2); 
                    arrayList.remove(pos);
                    nums2 = convertListToArray(arrayList);
                    
                    list.add(i);
                }
            }
            
            return convertListToArray(list);    
        }
        
        private int[] convertListToArray(ArrayList<Integer> list){
            if (list == null || list.size() < 1)
                return new int[0]; 
            
            int[] res = new int[list.size()];
            for(int i = 0; i < list.size(); i ++)
                res[i] = list.get(i);
            
            return res;
        }
        
        private ArrayList<Integer> convertArrayToList(int[] array){
            if (array == null || array.length < 1)
                return new ArrayList<Integer>(); 
            
            ArrayList<Integer> res = new ArrayList<Integer>(); 
            for (int i : array)
                res.add(i);
            return res; 
        }
        
        //Binary search, returns -1 if invalid, otherwise returns the position of x in array
        private int binarySearch(int[] arr, int x, int left, int right) { 
            if (arr == null || arr.length < 1)
                return -1; 
            if (left < right){
                int mid = left + (right - left)/ 2; 
                
                if (arr[mid] == x) {
                    return mid; 
                }
                else if (arr[mid] < x) //Search right wing
                    return binarySearch(arr, x, mid + 1, right);
                else if (arr[mid] > x) //Search left wing
                    return binarySearch(arr, x, left, mid); 
            } 
            return -1; 
        }
    }
    

Log in to reply
 

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