共计 4077 个字符,预计需要花费 11 分钟才能阅读完成。
1. 数组中是否存在某个值?
数组自带方法
var arr = [1, 2, 4, 3, 5, 6]
console.log(arr.includes(4))
console.log(arr.some(item => item === 4))
console.log(arr.find(item => item === 4))
console.log(arr.findIndex(item => item === 4))
console.log(arr.indexOf(4) !== -1)
console.log(arr.filter(item => item === 4))
// for 循环,略
其他各种 ” 神奇 ” 的算法
- 先排序,然后二分法查找
- set 解法,利用 set 的唯一性,将目标值添加进 set,如果 set 长度没变的话,这个值就是存在的
var arr = [1,2,3,4,5,6]
var arrSet = new Set(arr)
let prevSetLen = arrSet.size
arrSet.add(5)
console.log(prevSetLen===arrSet.length)
- 利用数组的 join 方法,把所有数字用逗号拼起来,然后正则匹配,或是调 includes 方法
2. 找出两个数组中的交集?
常规蠢办法
- for 循环
var arr1 = [1, 2, 3]
var arr2 = [3, 4, 5, 6]
var commonArr = []
for (var i = 0; i < arr1.length; i++) {var _item = arr1[i]
for (var j = 0; j < arr2.length; j++) {if (_item === arr2[j]) {commonArr.push(_item)
}
}
}
- ES6 的 filter 结合 includes 方法
var arr1 = [1, 2, 3]
var arr2 = [3, 4, 5, 6]
arr1.filter(item=>arr2.includes(item))
- 一个数组转对象,一个数组遍历看对象是否存在对应值
var arr1 = [1, 2, 3]
var arr2 = [3, 4, 5, 6]
var _obj = {}
let _tempArr = arr1.length > arr2.length ? arr2 : arr1
_tempArr.forEach(item => {_obj[item] = item
})
let commonArr = arr2.filter(item => _obj[item])
console.log(commonArr)
_obj = null
_tempArr = null
这里先判断数组长度,选一个短的数组,使得新创建的临时对象尽可能小。
- 如果不考虑单个数组里有重复项的话,可以先合并数组,然后再遍历合并后的数组,进行计次,大于 2 则是重叠的。
var arr1 = [1, 2, 3]
var arr2 = [3, 4, 5, 6]
var _tempArr = arr1.concat(arr2).sort()
var result = []
_tempArr.reduce((prev, now) => {if (prev === now) {result.push(now)
}
return now
})
- set 的使用,主要利用不可重复设置,判断长度是否有变化,而得出是否是重复了;或者直接用 has 方法
var arr1 = [1, 2, 3]
var arr2 = [3, 4, 5, 6]
var set = new Set(arr1)
var result = []
result = arr2.filter(item => arr1.has(item))
console.log(result)
“ 神奇 ” 的算法
- 排序后,两个数组下标移动,两两比较
var arr1 = [1, 2, 8, 3]
var arr2 = [5, 6, 2, 3, 4]
arr1.sort() // [1,2,3]
arr2.sort() // [2,3,4,5,6]
var result = []
let arr1Index = 0
let arr2Index = 0
let runTimes = 0
while (arr1Index < arr1.length && arr2Index < arr2.length) {
runTimes++
let arr1Item = arr1[arr1Index]
let arr2Item = arr2[arr2Index]
if (arr1Item > arr2Item) {arr2Index++} else if (arr1Item < arr2Item) {arr1Index++} else {result.push(arr1Item)
arr1Index++
arr2Index++
}
}
console.log(result)
console.log(runTimes)
3. 两个数组的并集?
- set
var arr1 = [1, 2, 3]
var arr2 = [4, 5, 3, 6]
var result = [...new Set(arr1.concat(arr2))]
// var result = [...new Set([...arr1, ...arr2])]
- reduce
var arr1 = [1, 2, 3]
var arr2 = [4, 5, 3, 6]
var tempArr = [...arr1, ...arr2].sort()
var result = []
tempArr.reduce((prev, now) => {if (prev !== now) {result.push(now)
}
return now
}, null)
console.log(result)
- 转 json 对象
var arr1 = [1, 2, 3]
var arr2 = [4, 5, 3, 6]
var obj = {}
arr1.forEach(item => (obj[item] = item))
arr2.forEach(item => (obj[item] = item))
var result = Object.values(obj)
console.log(result)
4. 数组去重?
效率上讲,转 obj 的方式 > set > reduce > includes/indexOf > 双重 for 循环
- 双重 for 循环
var arr1 = [1, 2, 3, 3, 4, 5, 6, 8]
var result = []
for (var i = 0; i < arr1.length; i++) {
let _hasItem = false
for (var j = 0; j < result.length; j++) {if (arr1[i] === result[j]) {
_hasItem = true
break
}
}
if (!_hasItem) {result.push(arr1[i])
}
}
console.log(result)
- includes/indexOf
var arr1 = [1, 2, 3, 3, 4, 5, 6, 8]
var result = []
arr1.forEach(item => {if (!result.includes(item)) {result.push(item)
}
})
- reduce
var arr1 = [1, 2, 4, 5, 3, 3, 3, 6, 8]
arr1.sort()
var result = []
arr1.reduce((prev, now) => {if (now !== prev) {result.push(now)
}
return now
}, null)
- set
var arr1 = [1, 2, 4, 5, 3, 3, 3, 6, 8]
var result = [...new Set(arr1)]
- 转对象方式
var arr1 = [1, 2, 4, 5, 3, 3, 3, 6, 8]
var obj = {}
arr1.forEach(item => (obj[item] = item))
var result = Object.values(obj)
5. 数组排序?
自带 sort
var arr = [2,3,1,4,6]
arr.sort(); // [1,2,3,4,6]
arr.sort((a,b)=>a-b); // [1,2,3,4,6]
arr.sort((a,b)=>b-a); // [6,4,3,2,1]
选择排序
每一次选择遍历选择一个最小值,确定一个位置
var times = 0
function selectSort(arr) {
// 没遍历一轮, 将确定一个位置
for (var i = 0; i < arr.length; i++) {
// 假定当前项是剩余未排中最小的
let minIndex = i
// 从已经确定的位置之后一位开始遍历
for (var j = i + 1; j < arr.length; j++) {
// 假如找到比 min 还小的, 更新最小值
if (arr[j] < arr[minIndex]) {minIndex = j}
}
// 得到最小值, 第 i 位确定
let temp = arr[i]
arr[i] = arr[minIndex]
arr[minIndex] = temp
}
}
冒泡排序
核心为两两按大小规则交换
function bubbSort(arr) {for (var i = 0; i < arr.length; i++) {
// 74
for (var j = i + 1; j < arr.length; j++) {
// 如果后面一个大于前面一个, 那么换位置
if (arr[j] < arr[i]) {var temp = arr[j]
arr[j] = arr[i]
arr[i] = temp
}
}
}
}
快速排序
- 先随机选一个数 (可选中间值)
- 以这个数分组,小的放左边,大的放右边
- 同理,在左边和右边的分组执行相同的操作,直到分组只剩一个元素
var arr = [74, 28, 60, 41, 29, 90, 52, 40]
function quickSort(arr){
// 递归出口
if(arr.length<=1){return arr}
// 1. 选中值
var basicNum = arr[Math.floor((arr.length - 1) / 2)]
// 2. 左右分组
var left = []
var right = []
arr.forEach(item=>{if(item>basicNum){right.push(item)
}
else{left.push(item)
}
})
// 3. 递归执行左边和右边数组, 并且合并结果
return quickSort(left).concat(basicNum, quickSort(right))
}
最简单也是空间复杂度高的排序,当前只能理解到这种了,以后理解了优化的再更新。????
归并排序,插入排序以后有时间再总结下
正文完
发表至: javascript
2019-06-30