Solution to followup 2


  • 0
    O

    public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
    HashMap<Integer, Integer> map = new HashMap<>();
    Arrays.sort(nums2);
    for(int i : nums1){
    if(map.containsKey(i)){
    map.put(i, map.get(i) + 1);
    }else{
    map.put(i, 1);
    }
    }
    List<Integer> list = new ArrayList<>();
    for(int key : map.keySet()){
    if(helper(nums2, key) > 0){
    for(int i = 0; i < Math.min(helper(nums2, key), map.get(key)); i++){
    list.add(key);
    }
    }
    }
    int i = 0;
    int[] res = new int[list.size()];
    for(int num : list){
    res[i] = num;
    i++;
    }
    return res;
    }

    public int helper(int [] nums, int target){
        if(nums.length == 0){
            return 0;
        }
        int left = -1;
        int start = 0;
        int end = nums.length - 1;
        while(start + 1 < end){
            int mid = (start + end) / 2;
            if(nums[mid] == target){
                end = mid;
            }else if(nums[mid] > target){
                end = mid;
            }else{
                start = mid;
            }
        }
        if(nums[start] == target){
                left = start;
        }else if(nums[end] == target){
                left = end;
        }
        if(left == -1){
            return 0;
        }
        int right = -1;
        start = 0;
        end = nums.length - 1;
        while(start + 1 < end){
            int mid = (start + end) / 2;
            if(nums[mid] == target){
                start = mid;
            }else if(nums[mid] > target){
                end = mid;
            }else{
                start = mid;
            }
        }
        if(nums[end] == target){
                right = end;
        }else if(nums[start] == target){
                right = start;
        }
        
        return right - left + 1;
    }
    

    }


Log in to reply
 

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