两个顺序排列的数组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;
}

Answer 2

function subset(A,B){
  A = A.slice();
  for(var i=0, len=B.length; i<len; i++){
    if(A.indexOf(B[i]) === -1){
       return false;
    }else{
      A.splice(A.indexOf(B[i]),1);
    }
  }
  return true;
}

Answer 3

function z(a, b) {
  var arr = [].concat(a);
  var index = -1;
  for(var i = 0; i < b.length; i++) {
     index = arr.indexOf(b[i]);
     if(arr.indexOf(b[i]) === -1) {
        return false
     }
     arr.splice(index, 1);
  }
  return true
}

看B是否是A的子集： z(A, B)

返回true就是，否则false不是

Answer 4

    //O(n)

    function isSubset(A, B) {
        let set = {};
        let res = 0;
        for (let i = 0; i < A.length; i++) {
            set['A' + A[i]] = 1;
            if (B[i]) {
                set['B' + B[i]] = set['B' + B[i]] ? set['B' + B[i]] + 1 : 1;
                res += 1;
                if (set['A' + B[i]]) {
                    res -= 1;
                    set['A' + B[i]] = 0;
                    set['B' + B[i]] -= 1;
                }
            }
            if (set['B' + A[i]]) {
                res -= 1;
                set['A' + A[i]] = 0;
                set['B' + A[i]] -= 1;
            }
        }
        return !res
    }
    
    console.log(isSubset([2, 1, 5, 3, 3, 3, 1], [1, 1, 2, 3, 3, 5]))