[刷题防痴呆] 0349 - 两个数组的交集 (Intersec

题目地址

https://leetcode.com/problems/intersection-of-two-arrays/description/

题目描述

349. Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Note:

Each element in the result must be unique.
The result can be in any order.

思路

• 第一种做法是用两个hashset. O(n).
• 第二种做法是用一个hashset, 一个binarySearch. O(nlogn).

关键点

• 注意, 二分的话, 需要先排序.

代码

• 语言支持：Java

// 方法1
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Set<Integer> intersect = new HashSet<>();
        
        for (int i = 0; i < nums1.length; i++) {
            set.add(nums1[i]);
        }
        for (int i = 0; i < nums2.length; i++) {
            if (set.contains(nums2[i])) {
                intersect.add(nums2[i]);
            }
        }
        
        int[] result = new int[intersect.size()];
        int index = 0;
        for (int num: intersect) {
            result[index++] = num;
        }
        
        return result;
    }
}
// 方法2
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) {
            return null;
        }
        Set<Integer> set = new HashSet<>();
        Arrays.sort(nums1);
        for (int num: nums2) {
            if (!set.contains(num)) {
                if (binarySearch(nums1, num)) {
                    set.add(num);
                }
            }
        }
        
        int[] result = new int[set.size()];
        int index = 0;
        for (int num: set) {
            result[index++] = num;
        }
        
        return result;
    }
    
    private boolean binarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return true;
            } else if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        if (nums[start] == target) {
            return true;
        }
        if (nums[end] == target) {
            return true;
        }
        return false;
    }
}