两个顺序排列的数组A和B 求B数组是否为A的子集(数组内肯呢个有重复的数字)?用js实现

Question

两个顺序排列的数组A和B 求B数组是否为A的子集(数组内肯呢个有重复的数字)?用js实现

Answer 1

写了一个，不过没有仔细测过。。。

好处就是和用indexOf,splice相比速度快很多，代码复杂度也小很多。。。

代码复杂度： O(n), 空间复杂度: O(1)

Array.prototype.isSubArrayOf = function(a){

  if(!a || !(a instanceof Array)) return false;

  let b = this;

  let aLength = a.length, bLength = b.length;

  if(aLength < bLength) return false;

  let indexA = 0, indexB = 0;

  while(indexB < bLength && indexA < aLength ) {

    let tempA = a[indexA], tempB = b[indexB];

    if(tempB === tempA) {

      indexA++;

      indexB++;

    } else if(tempB > tempA) {

      indexA++;

    } else {

      return false;

    }

  }

  return indexB === bLength;

}

非顺序排列数组，我把上面的判断删了，可以酌情加上：

代码复杂度： O(n+m), 空间复杂度: O(m)

Array.prototype.isSubArrayOf = function(a){

  let b = this, map = {};

  for(let i of b) {

    map[i] = map[i] ? map[i] + 1 : 1;

  }

  for(let i of a) {

    if(map[i]) { 

      map[i] = map[i] - 1;

      if(map[i] === 0) delete map[i];

    }

  }

  return Object.keys(map).length === 0;

}