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

Question

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

Answer 1

写了一个，不过没有仔细测过。。。好处就是和用indexOf,splice相比速度快很多，代码复杂度也小很多。。。代码复杂度：&nbsp;O(n), 空间复杂度:&nbsp;O(1)Array.prototype.isSubArrayOf = function(a){&nbsp; if(!a || !(a instanceof Array)) return false;&nbsp; let b = this;&nbsp; let aLength = a.length, bLength = b.length;&nbsp; if(aLength < bLength) return false;&nbsp; let indexA = 0, indexB = 0;&nbsp; while(indexB < bLength && indexA < aLength ) {&nbsp; &nbsp; let tempA = a[indexA], tempB = b[indexB];&nbsp; &nbsp; if(tempB === tempA) {&nbsp; &nbsp; &nbsp; indexA++;&nbsp; &nbsp; &nbsp; indexB++;&nbsp; &nbsp; } else if(tempB > tempA) {&nbsp; &nbsp; &nbsp; indexA++;&nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; }&nbsp; }&nbsp; return indexB === bLength;}非顺序排列数组，我把上面的判断删了，可以酌情加上：代码复杂度：&nbsp;O(n+m), 空间复杂度:&nbsp;O(m)Array.prototype.isSubArrayOf = function(a){&nbsp; let b = this, map = {};&nbsp; for(let i of b) {&nbsp; &nbsp; map[i] = map[i] ? map[i] + 1 : 1;&nbsp; }&nbsp; for(let i of a) {&nbsp; &nbsp; if(map[i]) {&nbsp;&nbsp; &nbsp; &nbsp; map[i] = map[i] - 1;&nbsp; &nbsp; &nbsp; if(map[i] === 0) delete map[i];&nbsp; &nbsp; }&nbsp; }&nbsp; return Object.keys(map).length === 0;}