求解两个数组的交集的方法

样题描述

方法说明

由于同一个数字在两个数组中都可能出现多次，因此需要用哈希表存储每个数字出现的次数。对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。

操作流程

首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。

注意:
为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。

java代码

package haxibiao;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

//两个数组的交集  350
public class Solutioon {
    public int[] intersect(int[] nums1, int[] nums2){
          if( nums1.length > nums2.length){
              intersect(nums2, nums1);    //如果nums1大于nums2时，交换两个数组
          }
          //创建一个哈希表
          Map<Integer,Integer> map = new HashMap<Integer,Integer>();
          for(int num: nums1){   //遍历数组nums1中的元素，count表示重复出现的元素的个数的
              int count = map.getOrDefault(num,0)+1;
              map.put(num, count); 
          }
          //创建一个用于存放输出结果的数组
          int[] intersection = new int[nums1.length];  
          int index = 0;
          for(int num : nums2){
              //得到遍历数组nums1时对应num元素的个数，该num元素和其对应的count存在哈希表中
              int count = map.getOrDefault(num, 0);
              if(count > 0){
                  //如果哈希表中对应元素的个数大于零，则将此时遍历nums2时的num放进创建的intersection数组中
                  intersection[index++] = num; 
                  count --;
                  if(count > 0){
                     map.put(num,count);//将num元素对应的个数count进行自减操作后，再放回哈希表中
                  }else{
                      map.remove(num); //如果num对应的个数值小于等于0就将这个数从哈希表中移除
                  }
              }
          }
        return Arrays.copyOfRange(intersection, 0, index);
    }
    public static void main(String[] args){
        int nums1[] = new int[]{4,9,5,4,4};
        int nums2[] = new int[]{9,4,9,8,4,6};
        Solutioon sool = new Solutioon();
        sool.intersect(nums1,nums2);
    }
}

思路总结

对于两个数组求其交集，首先创建一个哈希表，遍历两个数组中长度较短的，遍历nums1时将不同的数组元素放入到HashMap中，并且每次遍历时将遍历的元素个数加 1，直到数组元素遍历结束。遍历第二个数组的时候，首先创建一个数组用来存放两个数组的交集元素，，遍历第二个数组时，在
HashMap中寻找与第二个数组相等的元素，并将该数组元素相应的个数值取出来，赋值给count,，当count 大于零时，也就是HashMap中还有对应num的元素，此时进行的操作就是将这个第二个数组中此时的num值赋值给创建的 intersection 数组，并且将索引值index加 1,并且将count减 1，进行了上述操作后，如果count的值还是大于零，则将此时的 num 和 count 放入到 HashMap中，否则就将HashMap中这个元素移除，然后重复循环执行，知道循环结束，最后输出intersection 数组。