js求两个数组的交集

题目

leetcode-array

我的思路

  • 将数组nums1 转成map，然后数组2遍历，依次判断内部元素是否在nums1中，并且结果中不存在当前所遍历的nums2对象。代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    /**
     * @param {number[]} nums1
     * @param {number[]} nums2
     * @return {number[]}
     */
    var intersection = function(nums1, nums2) {
      let result = [];
      let originMap = {};
      for (let i = 0; i < nums1.length; i++) {
        if (originMap[nums1[i]]) {
          originMap[nums1[i]] += 1;
        } else {
          originMap[nums1[i]] = 1;
        }
      }

      for (let j = 0; j < nums2.length; j++) {
        if (originMap[nums2[j]] && (!result.includes(nums2[j]))) {
          result.push(nums2[j]);
        }
      }
      return result;
    }

  • 结果
    leetcode-array-result

以上执行用时还是很慢，想着如何优化

  • 看题解，发现有个思路比较有趣， 貌似是3s

  • 思路
    1） 把第一个数组排序
    2） 遍历第二个数组的值，判断是否在第一个数组中，这里使用的是二分法查找的数量

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    public int[] intersection(int [] nums1, int [] nums2) {
      Array.sort(nums1);

      Set(Integer) resSet = new HashSet<>();

      for(int i = 0; i < nums2.length; i++) {
        if (binarySearch(nums1, nums2[i]);
         resSet.add(nums2[i])
      }

      int [] res = new int[resSet.size()];
      int k = 0; 
      for (Integer num: resSet) {
        res[k++] = num;
      }

      return res; 
    }

    private boolean binarySearch(int [] nums, int target) {
      int left = 0;
      int right = nums.length - 1;
      while(left <= right) {
        int mid = left + (right - left) / 2;
        int midValue = nums[mid];

        if (midValue === target) {
          return true;
        } else if (midValue > target) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      }

      return false;
    }