扫码关注官方订阅号
两个顺序排列的数组A和B 求B数组是否为A的子集(数组内肯呢个有重复的数字)?用js实现
学习是最好的投资!
写了一个,不过没有仔细测过。。。
好处就是和用indexOf,splice相比速度快很多,代码复杂度也小很多。。。
indexOf
splice
代码复杂度: O(n), 空间复杂度: O(1)
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)
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; }
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; }
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不是
//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]))
微信扫码关注PHP中文网服务号
QQ扫码加入技术交流群
Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
PHP学习
技术支持
返回顶部
写了一个,不过没有仔细测过。。。
好处就是和用
indexOf,splice相比速度快很多,代码复杂度也小很多。。。代码复杂度:
O(n), 空间复杂度:O(1)非顺序排列数组,我把上面的判断删了,可以酌情加上:
代码复杂度:
O(n+m), 空间复杂度:O(m)看B是否是A的子集: z(A, B)
返回true就是,否则false不是