哈希——349. 两个数组的交集

梦里梦外; 2023-10-08 16:08 2阅读 0赞

## 1 题目描述 ##

1.  两个数组的交集  
    给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

## 2 题目示例 ##

示例 1：  
输入：nums1 = \[1,2,2,1\], nums2 = \[2,2\]  
输出：\[2\]

示例 2：  
输入：nums1 = \[4,9,5\], nums2 = \[9,4,9,8,4\]  
输出：\[9,4\]  
解释：\[4,9\] 也是可通过的

## 3 题目提示 ##

*  1 <= nums1.length, nums2.length <= 1000
 *  0 <= nums1\[i\], nums2\[i\] <= 1000

## 4 思路 ##

方法一:两个集合  
计算两个数组的交集，直观的方法是遍历数组nums1 ，对于其中的每个元素，遍历数组nums2判断该元素是否在数组nums2中，如果存在，则将该元素添加到返回值。假设数组nums1和nums2的长度分别是m和n，则遍历数组nums1需要O(m)的时间，判断nums1中的每个元素是否在数组nums2中需要O(n)的时间，因此总时间复杂度是O(mn)。如果使用哈希集合存储元素，则可以在O(1)的时间内判断一个元素是否在集合中，从而降低时间复杂度。  
首先使用两个集合分别存储两个数组中的元素，然后遍历较小的集合，判断其中的每个元素是否在另一个集合中，如果元素也在另一个集合中，则将该元素添加到返回值。该方法的时间复杂度可以降低到o(m + n)。  
复杂度分析  
· 时间复杂度:O(m + n)，其中m和n分别是两个数组的长度。使用两个集合分别存储两个数组中的元素需要o(m + n)的时间，遍历较小的集合并判断元素是否在另—个集合中需要O(min(m,rn))的时间，因此总时间复杂度是o(m ＋ n)。  
· 空间复杂度:O(m +n)，其中 m和n分别是两个数组的长度。空间复杂度主要取决于两个集合。

方法二:排序＋双指针  
如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。  
首先对两个数组进行排序，然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的，为了保证加入元素的唯一性，我们需要额外记录变量pre表示上一次加入答案数组的元素。  
初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，且该数字不等于pre，将该数字添加到答案并更新 pre变量，同时将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。  
复杂度分析

*  时间复杂度:O(m log m + n log n)，其中m和n分别是两个数组的长度。对两个数组排序的时间复杂度分别是(m log m)和O(n log n)，双指针寻找交集元素的时间复杂度是O(m +n)，因此总时间复杂度是O(m log m +n log n)。
 *  空间复杂度:O(log m + log n)，其中m和n分别是两个数组的长度。空间复杂度主要取决于排序使用的额外空间。

## 5 我的答案 ##

方法一：两个集合

class Solution {
        
        public int[] intersection(int[] nums1, int[] nums2) {
        
            Set<Integer> set1 = new HashSet<Integer>();
            Set<Integer> set2 = new HashSet<Integer>();
            for (int num : nums1) {
        
                set1.add(num);
            }
            for (int num : nums2) {
        
                set2.add(num);
            }
            return getIntersection(set1, set2);
        }
    
        public int[] getIntersection(Set<Integer> set1, Set<Integer> set2) {
        
            if (set1.size() > set2.size()) {
        
                return getIntersection(set2, set1);
            }
            Set<Integer> intersectionSet = new HashSet<Integer>();
            for (int num : set1) {
        
                if (set2.contains(num)) {
        
                    intersectionSet.add(num);
                }
            }
            int[] intersection = new int[intersectionSet.size()];
            int index = 0;
            for (int num : intersectionSet) {
        
                intersection[index++] = num;
            }
            return intersection;
        }
    }

方法二：排序 + 双指针

class Solution {
        
        public int[] intersection(int[] nums1, int[] nums2) {
        
            Arrays.sort(nums1);
            Arrays.sort(nums2);
            int length1 = nums1.length, length2 = nums2.length;
            int[] intersection = new int[length1 + length2];
            int index = 0, index1 = 0, index2 = 0;
            while (index1 < length1 && index2 < length2) {
        
                int num1 = nums1[index1], num2 = nums2[index2];
                if (num1 == num2) {
        
                    // 保证加入元素的唯一性
                    if (index == 0 || num1 != intersection[index - 1]) {
        
                        intersection[index++] = num1;
                    }
                    index1++;
                    index2++;
                } else if (num1 < num2) {
        
                    index1++;
                } else {
        
                    index2++;
                }
            }
            return Arrays.copyOfRange(intersection, 0, index);
        }
    }