LeetCode349-Intersection of Two Arrays

题目

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

Example:

Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Notes:

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

分析

解法一:HashSet查找

题意很明确,求两个数组的交集,不含重复元素。利用HashSet<Integer>存储num2中的数,然后遍历num1所有元素,依次判断是否存在于set中,若存在证明加入结果集合(也是HashSet<Integer>集合,为防止重复)。击败33%的人。

解法二:二分查找

第二种方式大致思路一致,只是在对num2的查找方式上采用的是先排序再二分查找。击败29%的人。

解法三:双指针查找

第三种方式更为奇妙:先对两个数组排序,然后用双指针i和j作为游标,分别指向num1和num2:

  • 若num1[i] = num2[j]:相交,加入集合
  • 若num1[i] < num2[j]:i++,j不动,因为只有num1[i]增大才可能找到相等元素
  • 若num1[i] > num2[j]:j++,i不动,因为只有num2[j]增大才可能找到相等元素

代码

解法一

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<Integer>();
        Set<Integer> findSet = new HashSet<Integer>();
        
        //将nums2装入查找表
        for (Integer num : nums2)
            findSet.add(num);
        
        //排序
        Arrays.sort(nums1);
        
        int i;
        for (i = 0; i < nums1.length; i++) {
            
            //查找nums1[i]是否在nums2中
            if(findSet.contains(nums1[i])) {
                set.add(nums1[i]);
            }
        }

        //复制到int[]
        int[] res = new int[set.size()];
        i = 0;
        for (Integer num : set)
            res[i++] = num;
        
        return res;
    }
}

解法二

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {

        HashSet<Integer> set = new HashSet<Integer>();

        //排序
        Arrays.sort(nums2);
        
        int i;
        for (i = 0; i < nums1.length; i++) {
            
            //二分查找nums1[i]是否在数组nums2中
            if(binarySearch(nums2, 0, nums2.length - 1, nums1[i])){
                set.add(nums1[i]);
            }
        }
        
        //复制到int[]
        int[] res = new int[set.size()];
        i = 0;
        for (Integer num : set)
            res[i++] = num;
        
        return res;
    }
    
    //查找target是否在数组nums的low-high区间内
    boolean binarySearch(int[] nums, int low, int high, int target) {
        int mid;
        while (low <= high) {
            mid = (low + high) / 2;
            if (target > nums[mid]) low = mid + 1;
            else if (target < nums[mid]) high = mid - 1;
            else return true; //找到
        }
        
        return false;
    }
}

解法三

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        
        HashSet<Integer> set = new HashSet<Integer>();

        //排序
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        //两指针移动比较
        int i = 0;
        int 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 {
                j++;
            }
        }
        
        //复制到int[]
        int[] res = new int[set.size()];
        i = 0;
        for (Integer num : set)
            res[i++] = num;
        
        return res;
    }
}

Leave a Comment.