交集.md

交集

例如：给定 nums1 = [1, 2, 2, 1]，nums2 = [2, 2]，返回 [2, 2]

解答

1. 暴力解法

function intersect (arr1, arr2) {
  var res = []
  
  for (var i = 0; i < arr1.length; i++) {
    for (var j = 0; j < arr2.length; j++) {
      var index = arr2.indexOf(arr1[i])
      if (index !== -1) {
        res.push(arr1[i])
        arr2.splice(index, 1)
      } 
    } 
  }  
  
  return res
}

2. 哈希表

function intersect (arr1, arr2) {
  var hash = {}
  var res = []
  for (var i = 0; i < arr1.length; i++) { 
    var item = arr1[i]
    hash[item] = hash[item] ? hash[item] + 1 : 1
  }
  
  for (var j = 0; j < arr2.length; j++) {
    var item = arr2[j]
    if (hash[item]) {
      res.push(item)
      hash[arr2[j]] = item - 1
    } 
  } 
  
  return res
}

3. 双指针

function intersect (arr1, arr2) {
  var s1 = arr1.sort((a, b) => a - b)
  var s2 = arr2.sort((a, b) => a - b)
  var i = 0
  var j = 0
  var res = []
  
  while(i < arr1.length && j < arr2.length) {
    if (s1[i] === s2[j]) {
      res.push(s1[i])
      i++
      j++
    } else if (s1[i] > s2[j]) {
      j++
    } else {
      i++
    }
  }
  
  return res
}