349. 两个数组的交集
350. 两个数组的交集 II

参考链接：https://leetcode-cn.com/problems/intersection-of-two-arrays/solution/duo-chong-jie-fa-jie-jue-349-liang-ge-shu-zu-de-ji/

349. 两个数组的交集

Set

参考链接：https://leetcode-cn.com/problems/intersection-of-two-arrays/solution/duo-chong-jie-fa-jie-jue-349-liang-ge-shu-zu-de-ji/

 public int[] intersection(int[] nums1, int[] nums2) {
    if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
      return new int[0];
    }
    Set<Integer> parentSet = new HashSet<>();
    Set<Integer> childSet = new HashSet<>();
    for (int num : nums1) {
      parentSet.add(num);
    }
    for (int num : nums2) {
      if (parentSet.contains(num)) {
        childSet.add(num);
      }
    }
    int[] resArr = new int[childSet.size()];
    int index = 0;
    for (int value : childSet) {
      resArr[index++] = value;
    }
    return resArr;
  }

双指针

不用set

自己写的

    public int[] intersection1(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> res = new LinkedList<>();
        int p1=0;
        int p2=0;
        int len1=nums1.length;
        int len2=nums2.length;
        while(p1<len1 && p2<len2){
            if(nums1[p1]==nums2[p2]){
                res.add(nums1[p1]);
                p1++;
                p2++;
                while(p1<len1 && nums1[p1]==nums1[p1-1]){
                    p1++;
                }
                while(p2<len2 && nums2[p2]==nums2[p2-1]){
                    p2++;
                }
            }else if(nums1[p1]<nums2[p2]){
                while(p1<len1 && nums1[p1]<nums2[p2]){
                    p1++;
                }
            }else{
                while(p2<len2 && nums1[p1]>nums2[p2]){
                    p2++;
                }
            }
        }
        int[] ans = new int[res.size()];
        for(int i=0;i<res.size();i++){
            ans[i]=res.get(i);
        }
        return ans;
    }

用set

参考链接 https://leetcode-cn.com/problems/intersection-of-two-arrays/solution/duo-chong-jie-fa-jie-jue-349-liang-ge-shu-zu-de-ji/

public int[] intersection(int[] nums1, int[] nums2) {
  Set<Integer> set = new HashSet<>();
  Arrays.sort(nums1);
  Arrays.sort(nums2);
  int i = 0, j = 0;
  while (i < nums1.length && j < nums2.length) {
    if (nums1[i] == nums2[j]) {
      set.add(nums1[i]);
      i++;
      j++;
    } else if (nums1[i] < nums2[j]) {
      i++;
    } else if (nums1[i] > nums2[j]) {
      j++;
    }
  }
  int[] res = new int[set.size()];
  int index = 0;
  for (int num : set) {
    res[index++] = num;
  }
  return res;
}

二分法

不用set

自己写的

    public int[] intersection(int[] nums1, int[] nums2){
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> res = new LinkedList<>();
        int len1=nums1.length;
        for(int i=0;i<len1;){
            int num=nums1[i];
            if(binarySearch(nums2, num)){
                res.add(num);
            }
            i++;
            while(i<len1 && nums1[i]==nums1[i-1]){
                i++;
            }
        }
        int[] ans = new int[res.size()];
        for(int i=0;i<res.size();i++){
            ans[i]=res.get(i);
        }
        return ans;
    }

    private boolean binarySearch(int[] nums, int target){
        int len=nums.length;
        int left=0;
        int right=len-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target){
                return true;
            }else if(nums[mid]<target){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return false;
    }

用set

参考链接 https://leetcode-cn.com/problems/intersection-of-two-arrays/solution/duo-chong-jie-fa-jie-jue-349-liang-ge-shu-zu-de-ji/

public int[] intersection(int[] nums1, int[] nums2) {
  Set<Integer> set = new HashSet<>();
  Arrays.sort(nums2);
  for (int target : nums1) {
    if (binarySearch(nums2, target) && !set.contains(target)) {
      set.add(target);
    }
  }
  int index = 0;
  int[] res = new int[set.size()];
  for (int num : set) {
    res[index++] = num;
  }
  return res;
}
public boolean binarySearch(int[] nums, int target) {
  int left = 0, right = nums.length - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
      return true;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else if (nums[mid] < target) {
      left = mid + 1;
    }
  }
  return false;
}

350. 两个数组的交集 II

Map

参考链接：https://leetcode-cn.com/problems/intersection-of-two-arrays/solution/duo-chong-jie-fa-jie-jue-349-liang-ge-shu-zu-de-ji/

public int[] intersect(int[] nums1, int[] nums2) {
    List<Integer> list = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums1) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    for (int num : nums2) {
        if (map.containsKey(num) && map.get(num) > 0) {
            list.add(num);
            map.put(num, map.get(num) - 1);
        }
    }
    int[] res = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        res[i] = list.get(i);
    }
    return res;
}

双指针

自己写的

    public int[] intersect1(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> res = new LinkedList<>();
        int p1=0;
        int p2=0;
        int len1=nums1.length;
        int len2=nums2.length;
        while(p1<len1 && p2<len2){
            if(nums1[p1]==nums2[p2]){
                res.add(nums1[p1]);
                p1++;
                p2++;
                // while(p1<len1 && nums1[p1]==nums1[p1-1]){
                //     p1++;
                // }
                // while(p2<len2 && nums2[p2]==nums2[p2-1]){
                //     p2++;
                // }
            }else if(nums1[p1]<nums2[p2]){
                while(p1<len1 && nums1[p1]<nums2[p2]){
                    p1++;
                }
            }else{
                while(p2<len2 && nums1[p1]>nums2[p2]){
                    p2++;
                }
            }
        }
        int[] ans = new int[res.size()];
        for(int i=0;i<res.size();i++){
            ans[i]=res.get(i);
        }
        return ans;
    }

二分法

自己写的

    public int[] intersect(int[] nums1, int[] nums2){
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> res = new LinkedList<>();
        int len1=nums1.length;
        for(int i=0;i<len1;){
            int num=nums1[i];
            int firstIndex=binarySearchFirstIndex(nums2, num);
            if(firstIndex!=-1){
                int lastIndex=binarySearchLastIndex(nums2, num);
                int count2=lastIndex-firstIndex+1;
                int count1=1;
                i++;
                while(i<len1 && nums1[i]==nums1[i-1]){
                    i++;
                    count1++;
                }
                int count=Math.min(count1,count2);
                for(int j=0;j<count;j++){
                    res.add(num);
                }
            }else{
                i++;
                while(i<len1 && nums1[i]==nums1[i-1]){
                    i++;
                }
            }
        }
        int[] ans = new int[res.size()];
        for(int i=0;i<res.size();i++){
            ans[i]=res.get(i);
        }
        return ans;
    }

    private int binarySearchFirstIndex(int[] nums, int target){
        int len=nums.length;
        int left=0;
        int right=len-1;
        int res=-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target){
                res=mid;
                right=mid-1;
            }else if(nums[mid]<target){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return res;
    }

    private int binarySearchLastIndex(int[] nums, int target){
        int len=nums.length;
        int left=0;
        int right=len-1;
        int res=-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target){
                res=mid;
                left=mid+1;
            }else if(nums[mid]<target){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return res;
    }