数组 - 不知名的笔记本

本文最后更新于：2022年6月7日中午

创建数组

// 字面量
let arr = []
let arr = [1,2,3,4]
// 构造函数
let arr = new Array()
let arr = new Array(/传入数组代表数组长度/)
let arr = new Array('item1','item2'/传入元素/)
let arr = Array(10)/省略new操作符/
// Array.of
Array.of(7) 创建一个具有单个元素 7 的数组，而
Array(7) 创建一个长度为7的空数组
// Array.from
Array.from(arrayLike[, mapFn[, thisArg]]类数组对象)

变异方法（改变原数组）

pop()删除最后一个元素
shift()删除第一个元素
push()添加元素至末尾
unshift()添加元素至首位
splice(start,delCount,new1,new2...)往数组索引为 start 位置删除 delCont 个元素，并从该位置加入 new 新元素
sort()排序
reverse()倒序,返回新数组
es6
copyWithin(target,start,end)拷贝数组中索引从 start 到 end（end）的元素添加至 target
fill(value,start,end)将数组中索引 start 到 end（不含）的位置填充为 value 元素

非变异方法

slice(start,end)潜拷贝，返回索引从 start 到 end（不含）的元素组成新数组
join()指定分隔符将数字元素连成字符串
concat()合并数组
indexOf()/lastIndexOf()查找元素索引,可传入起始位置
includes()查找是否包含元素返回 Boolean,可传入起始位置
...展开运算符

遍历数组

遍历数组的回调mapFn包含自动传入的参数(currentValue,currentIndex,thisArr)

// parseInt(string, radix)   解析一个字符串并返回指定基数的十进制整数
// 解释了
['1','2','3'].map(parseInt)
=>  parseInt('1',0),parseInt('2',1),parseInt('3',2)
=>  1,NaN,NaN

map()使用指定函数映射每一个元素后的返回值组成的新数组
flatmap()使用指定函数映射每一个元素后的返回值组成新数组并执行一次扁平化
some()测试是否至少有一个元素可以通过提供的函数,返回布尔值，找到第一个就会停止遍历
every()检测数组所有元素是否都符合判断条件,返回布尔值，遇到false就会停止遍历
forEach()对数组的每个元素执行一次提供的函数,不会改变原数组
filter()返回通过制定函数过滤后「返回true」的数组
find()返回数组中满足提供的测试函数的第一个元素的值。否则返回 undefined
findIndex()返回数组中满足提供的测试函数的第一个元素的索引。否则返回-1
reduce()和reduceRight()累加器,累加函数的 return 作为下一次累加的 pre 值，并可指定初始值
flat(depth)按照一个可指定的深度递归遍历数组，并将所有元素与遍历到的子数组中的元素合并为一个新数组返回（_会移除数组中的空项_）

调用遍历器[Symbol.Iterator]

of Object.keys()
of Object.values()
of Object.entries()

for (let index of ["a", "b"].keys()) {
	console.log(index);
}
// 0
// 1
for (let elem of ["a", "b"].values()) {
	console.log(elem);
}
// 'a'
// 'b'
for (let [index, elem] of ["a", "b"].entries()) {
	console.log(index, elem);
}
// 0 "a"
// 1 "b"

判断数组

arr.constructor===Array
arr instanceof Array
Array.prototype.isPrototypeOf(arr)

这三种查找原型的方法，如果手动更改对象的原型也可欺骗过检测
Object.prototype.toString.call(arr)==='[object Array]'
Array.isArray()

const notArr = {
	__proto__: Array.prototype,
};
notArr.constructor = Array;
// true
Array.prototype.isPrototypeOf(notArr);
// true
notArr instanceof Array;
// true
Object.prototype.toString.call(notArr);
// "[object Object]"
Array.isArray(notArr);
// false

数组去重

let arr = [1, 1, 2, 2, 3, 3, 4, 4, 4, 4];
// 1
let uni1 = Array.from(new Set(arr));
// 2
let uni2 = [...new Set(arr)];
// 3
let uni3 = arr.sort().reduce((pre, cur) => {
	if (pre.length === 0 || pre[pre.length - 1] !== cur) pre.push(cur);
	return pre;
}, []);
// 4
let uni4 = arr.reduce((pre,cur)=>{
	if(!pre.includes(cur)){
		pre.push(cur)
	}
	return pre
},[])
// 5
let uni4 = arr.filter((item, index) => {
	return arr.indexOf(item) === index;
});

计算数组中元素出现的次数

let arr = [1, 1, 2, 2, 3, 3, 4, 4, 4, 4];
//reduce
let countArr = arr.reduce((obj, i) => {
	if (obj[i]) {
		obj[i]++;
	} else {
		obj[i] = 1;
	}
	return obj;
}, {});

// { '1': 2, '2': 2, '3': 2, '4': 4 }
// 循环
let obj = {};
for (let i of arr) {
	if (i in obj) {
		obj[i]++;
	} else {
		obj[i] = 1;
	}
}

对于 obj 按照属性分类

// 面试题教你归类json
// JSON.parse(jsonStr)
let person = [
	{ name: "Alice", age: 21 },
	{ name: "Bob", age: 21 },
	{ name: "Hank", age: 20 },
	{ name: "Jery", age: 19 },
];

function groupBy(objArr, prop) {
	return objArr.reduce((acc, obj) => {
		let key = obj[prop];
		if (!acc[key]) acc[key] = [];
		acc[key].push(obj);
		return acc;
	}, {});
}

let res = groupBy(person, "age");

扁平化数组

// 1 reduce
function flat1(arr) {
  return arr.reduce((res, item) =>  {
    return res.concat(Array.isArray(item) ? flat1(item) : item);
  }, []);
}
//2 递归
function flat2(arr) {
  let res = [];
  for (let item of arr) {
    res.push(Array.isArray(item) ? (...flat2(item)) : item)
  }
  return res;
}
// 3 展开运算符
function flat3(arr) {
  while (arr.some((item) =>  Array.isArray(item))) {
    arr = [].concat(...arr);
  }
  return arr;
}
// 4 toString
function flat4(arr) {
  return arr
    .toString()
    .split(",")
    .map((item) =>  Number(item));
}
// 5 join
function flat5(arr) {
  return arr
    .join(",")
    .split(",")
    .map((item) =  Number(item));
}
// 6 flat()
flat(Infinity);

数组排序

V8 中的 sort()

7.0 之前 arr.length = 10【插入排序】， > 10【快速排序】
7.0 之后【timesort】

常见排序方法

冒泡排序

O(n^2) 第一个循环设定冒泡范围，第二个循环冒泡元素

function bubbleSort(arr) {
	if (!Array.isArray(arr) || arr.length < 2) return arr;
	const len = arr.length;
	// 外层循环是冒泡范围
	for (let i = 0; i < len; i++) {
		let flag = false; // 提前退出flag
		// 内层循环是冒泡比较
		for (let j = 1; j < len - i; j++) {
			if (arr[j - 1] > arr[j]) {
				[arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
				flag = true;
			}
		}
		if (flag === false) return;
	}
	return arr;
}

插入排序

O(n^2)

function insertSort(arr) {
	if (!Array.isArray(arr) || arr.length < 2) return arr;
	const len = arr.length;

	for (let i = 1; i < len; i++) {
		const pivot = arr[i]; // 从index开始选出基准值
		let j = i;
		while (arr[j - 1] > pivot && j > 0) {
			// 与基准值比较,将基准值插入正确位置
			arr[j] = arr[j - 1]; // 把比基准大的元素向右边搬移
			j--;
		}
		arr[j] = pivot;
	}
	return arr;
}

// 也可以使用交换,性能低
function insertSort2(arr) {
	const len = arr.length;
	if (len < 2) return arr;
	for (let i = 1; i < len; i++) {
		for (let j = i; j > 0 && arr[j] > arr[j - 1]; j--) {
			[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
		}
	}
	return arr;
}

选择排序

O(n^2) 不稳定

function selectSort(arr) {
	if (Array.isArray(arr) !== true || arr.length < 2) return arr;
	const len = arr.length;
	for (let i = 0; i < len - 1; i++) {
		let minIndex = i;
		// 假设i为从i到len的最小值
		for (let j = i + 1; j < len; j++) {>
			// 从i+1开始寻找最小值
			if (arr[j] < arr[minIndex]) {
				minIndex = j;
			}
		}
		// 替换i位置的值得
		[arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
	}
	return arr;
}

对于大量数据,上述三种 O(n^2)的时间复杂度难以接受

并归排序

O(n log n)

function mergeSort(arr) {
	if (arr.length === 1) return arr;
	// once function 'mergeSort' run ,split arr to two group length equally
	const mid = Math.floor(arr.length / 2);
	const left = arr.slice(0, mid);
	const right = arr.slice(mid);
	return merge(mergeSort(left), mergeSort(right));
}
function merge(l, r) {
	const res = [];
	while (l.length > 0 && r.length > 0) {
		//notice: ‘&&’ not ‘||‘
		if (l[0] > r[0]) {
			res.push(r.shift());
		} else {
			res.push(l.shift());
		}
	}
	// one of l and r is empty,concat it to Array 'res'
	return res.concat(l).concat(r);
}

快速排序

平均 O(n log n)

function quickSort(arr){
  if (arr.length <= 1) return arr; //一直排序到区间内只有一个数
  var pivotIndex = Math.floor(arr.length / 2); //基准位置（可任意选取）
  var pivot = arr.splice(pivotIndex, 1)[0]; //找出基准数并把它从原数组删除
  var left = [];  // 空间复杂度O(n)
  var right = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
			// 小于在左边大于在右
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return [...quickSort(left), pivot, ...quickSort(right)]
}


// 不使用额外空间,在原数组交换元素位置
function quickSort(arr) {
  function quick(arr,l,r){
    const index = partition(arr,l,r)
    // partition函数取出一个基准索引并将该索引的元素放到顺序正确的位置
    if(l<index){
      quick(arr,l,index-1)
    }
    if(r>index){
      quick(arr,index+1,r)
    }
  }
  quick(arr,0,arr.length-1)
  return arr
}
// 选取一个参考位置，并将该位置的元素移动到排序后的位置，即左边都小于他右边都大于他
function partition(arr,l,r){
  // 这里直接使用r作为基准，不用随机值
	const pivotValue = arr[r]
	const pivotIndex = l

  // pivotIndex 是排序后pivot的正确位置，初始设置为最左
  for(let j = l ; j<r ; j++){
    // 判断相对于基准的大小并更新i的位置
    // i左边是已经比较完的区间,都比arr[r]小
    if(arr[j]<pivotValue){
      [arr[j],arr[pivotIndex]] = [arr[pivotIndex],arr[j]]// j向右扫的过程中遇到比基准小的值时,i停留在上一个比基准大的位置,则对他两进行交换
      pivotIndex++
    }
  }
  // pivot归位,最后以i位置完成分界
  [arr[pivotIndex],arr[r]] = [arr[r],arr[pivotIndex]]
  return pivotIndex
}

希尔排序

平均 O(n log 2n) 最坏 O(n^2)
相当于设置动态间隔的插入排序

// 移动
function shellSort1(arr) {
	const len = arr.length;
	if (len < 2) return arr;
	// 这里初始设为长度一半
	for (let gap = len >> 1; gap > 0; gap = gap >> 1) {
		// 不断缩小间隔的长度
		// 最终会为1
		for (let i = gap; i < len; i++) {
			const pivot = arr[i];
			let j = i;
			while (arr[j - gap] > pivot && j - gap >= 0) {
				arr[j] = arr[j - gap];
				j -= gap;
			}
			arr[j] = pivot;
		}
	}
	return arr;
}

堆排序

// 建立大顶堆
// 依次将末尾元素与heap[1]交换位置并调整堆，同时缩小堆的大小（排除最后的大数）
// heap[2]和heap[1]交换完成后就是升序排序
function heapSort(arr) {
	const heap = [, ...arr];
	let heapSize = arr.length;
	buildHeap(heap, heapSize);
	// 开始交换头尾
	for (let k = heapSize; k > 1; k--) {
		[heap[k], heap[1]] = [heap[1], heap[k]];
		heapify(heap, --heapSize, 1);
	}
	heap.shift();

	function buildHeap(heap, size) {
		for (let i = Math.floor(size / 2); i >= 1; i--) {
			heapify(heap, size, i);
		}
	}
	function heapify(heap, heapSize, i) {
		while (true) {
			let maxIndex = i;
			if (2 * i <= heapSize && heap[2 * i] > heap[i]) maxIndex = 2 * i;
			if (2 * i + 1 <= heapSize && heap[2 * i + 1] > heap[maxIndex]) maxIndex = 2 * i + 1;
			if (maxIndex === i) break;
			[heap[maxIndex], heap[i]] = [heap[i], heap[maxIndex]];
			i = maxIndex;
		}
	}
}

记数排序🤯

function countSort(arr) {
	let maxValue = arr[0];
	for (let n of arr) {
		if (n > maxValue) maxValue = n;
	}
	// 找出数据中的最大值

	const countArr = Array(maxValue + 1).fill(0);
	// 建立计数数组，下标为数据值，元素为相同元素个数

	for (let n of arr) {
		countArr[n]++;
	}
	// 统计数据出现次数加入计数数组

	// 对计数数组执行累加操作
	for (let i = 1; i < countArr.length; i++) {
		countArr[i] += countArr[i - 1];
	}
	// countArr中元素即代表arr中元素小于等于该下标的数量

	const temp = Array(arr.length);
	for (let j = arr.length - 1; j >= 0; j--) {
		let num = arr[j];
		let pos = countArr[num] - 1;
		// 得出顺序正确的索引
		temp[pos] = num;
		// arr指针向左扫，归位元素后将累加计数数组中计数-1
		countArr[num]--;
	}
	return temp; // or copy temp to origin arr
}

洗牌算法

function shuffle(arr) {
	return arr.sort(() => Math.random() - 0.5);
	//由于js中sort方法的特殊性，对于数据量小于10和大于10的排序方法不一样
	// Math.random()-0.5不能做到真正意义上的完全随机
}

function shuffle(arr) {
	let len = arr.length;
	while (len) {
		const i = (Math.random() * len) >> 0
		// 随机位置和末尾交换
		[arr[i], arr[len-1]] = [arr[len-1], arr[i]];
		len -- 
		// const i = (Math.random() * len--) >> 0;
		// [arr[i], arr[len]] = [arr[len], arr[i]];
	}
	return arr;
}

#javascript

数组

http://yoursite.com/2022/02/24/数组/

作者

tatekii

发布于

2022年2月24日

许可协议

vue组件之间通信方式上一篇

栈算法题下一篇