本文共 1958 字，大约阅读时间需要 6 分钟。

1、给定两个数组，编写一个函数来计算它们的交集。

示例 1：输入：nums1 = [1,2,2,1], nums2 = [2,2]输出：[2,2]示例 2:输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出：[4,9]

方法1：哈希表

public int[] intersect(int[] nums1,int[] nums2) {
   		if(nums1.length>nums2.length) {
   			return intersect(nums2,nums1);		}		Map
   
    map=new HashMap
    
     ();		for(int num:nums1) {
   			int count=map.getOrDefault(num, 0)+1;			map.put(num,count);		}		int[] intersection=new int[nums1.length];		int index=0;		for(int num:nums2) {
   			int count=map.getOrDefault(num, 0);			if(count>0) {
   				intersection[index++]=num;				count--;				if(count>0) {
   					map.put(num,count);				}else {
   					map.remove(num);				}			}		}		return Arrays.copyOfRange(intersection, 0, index);	}
    
   

时间复杂度：O(m+n)，其中 m和 n分别是两个数组的长度。需要遍历两个数组并对哈希表进行操作，哈希表操作的时间复杂度是 O(1)，因此总时间复杂度与两个数组的长度和呈线性关系。空间复杂度：O(min(m,n))，其中 m 和 n 分别是两个数组的长度。对较短的数组进行哈希表的操作，哈希表的大小不会超过较短的数组的长度。为返回值创建一个数组 intersection，其长度为较短的数组的长度。

方法2：排序

class Solution {
       public int[] intersect(int[] nums1, int[] nums2) {
           Arrays.sort(nums1);        Arrays.sort(nums2);        int length1 = nums1.length, length2 = nums2.length;        int[] intersection = new int[Math.min(length1, length2)];        int index1 = 0, index2 = 0, index = 0;        while (index1 < length1 && index2 < length2) {
               if (nums1[index1] < nums2[index2]) {
                   index1++;            } else if (nums1[index1] > nums2[index2]) {
                   index2++;            } else {
                   intersection[index] = nums1[index1];                index1++;                index2++;                index++;            }        }        return Arrays.copyOfRange(intersection, 0, index);    }}

时间复杂度：O(mlogm+nlogn)，其中 mm 和 nn 分别是两个数组的长度。对两个数组进行排序的时间复杂度是 O(mlogm+nlogn)，遍历两个数组的时间复杂度是 O(m+n)，因此总时间复杂度是 O(mlogm+nlogn)。空间复杂度：O(min(m,n))，其中 m 和 n 分别是两个数组的长度。为返回值创建一个数组 intersection，其长度为较短的数组的长度。不过在 C++ 中，我们可以直接创建一个 vector，不需要把答案临时存放在一个额外的数组中，所以这种实现的空间复杂度为 O(1)。

转载地址：http://ikgwi.baihongyu.com/