数据结构与算法-数组

前言：

几乎所有的编程语言都原生支持数组类型。因为数组是最简单的内存数据结构。

创建一个数组：

let arr = new Array()

或

let arr = new Array(5) // 指定长度

或

let arr = new Array(1,2,3,4,5) // 将数组元素作为参数传给构造函数

或

let arr = [1,2,3,4,5] // 中括号创建数组

访问元素和迭代数组：

for (let i = 0; i < arr.length; i ++) {console.log(arr[i])}

斐波那契数列

已知斐波那契数列的前三项分别是0,1,1，从第三项开始，每一项都等于前两项之和。求斐波那契数列前20个数。

const arr = new Array(20);
arr[0] = 0;
arr[1] = 1;
arr[2] = 1;
for (let i = 3;i<arr.length;i++) {arr[i] = arr[i-1] + arr[i-2]
}

斐波那契数列的经典算法面试题可以看这篇推文->斐波那契数列的算法

添加数组元素

1、在末尾插入元素

在js中，数组是一个可以修改的对象。如果添加元素，它会动态的增长。在其他语言如C和java中，想添加元素需要创建一个全新的数组。不能直接往里面添加元素

arr[arr.length] = 10

或

arr.push(10) //一个

arr.push(10,11) //两个

2、在开头插入元素

arr.unshift(-1)//一个
arr.unshift(-1,-2)//两个

不用unshift怎么实现在开头插入一个元素

var arr = [3,4,5,6]
for (var i = arr.length;i>0;i--){arr[i] = arr[i-1]
}
arr[0] = 2

3、在数组末尾删除元素

arr.pop();

push和pop方法都是用数组模拟栈。

4、在数组开头删除元素

arr.shift();

不用shift怎么实现在开头删除一个元素

Array.prototype.move= function() {for(var i =0;i<this.length;i++){this[i] = this[i+1]}return this.removeUndefined()
}
Array.prototype.removeUndefined = function(){const newArr = [];for (var i = 0; i< this.length;i++) {if (this[i] !== undefined) {newArr.push(this[i])}}return newArr
}
// -----------------------------------------------
var arr = [3,5,6,7,8]
arr.move() // [5,6,7,8]

5、任意位置添加或删除元素

arr.splice(_index,_number,[element]);
// _index:删除或插入的下标
// _number个数
// [element]替换的元素

二维数组(矩阵)

js只支持一维数组，我们可以用数组套数组，实现二维数组（矩阵）或多维数组。

const dataModel = [[65,23,45],[21,11,77]
]

迭代二维数组的元素

for(let i = 0;i < dataModel.length;i++) {for (let j = 0;j < dataModel[i].length;j++) {console.log(dataModel[i][j])}
}

多维数组

// 三维数组
const arr = new Array();
arr[0] = [];
arr[0][0] = [1];
arr[0][0][0] =1;

创建一个3*3正方形魔方立体矩阵

const arr = [];
const r = 3; // 正方体边长
for (var x =0;x<r;x++) {arr[x] = []; //必须层层初始化数组for (var y=0;y<r;y++) {arr[x][y] = [];for (var z=0;z<r;z++) {arr[x][y][z] = x+y+z;}}
}

魔方中最小的值为0+0+0等于0，最大的值为2+2+2=6

循环遍历三维数组

for (var x = 0; x< arr.length; x++) {for (var y =0;y<arr[x].length;y++) {for (var z = 0;z<arr[x][y].length;z++) {console.log(arr[x][y][z])}}
}

四维数组使用极少，在此不表。

常用数组方法

方法名	对应版本	功能	原数组改变
concat①	-	合并数组，并返回合并之后的数据	x
forEach	ES5	遍历数组所有的项。接收回调参数为传参。回调函数接受三个参数，分别为value，index，self；无返回值	x
every	ES5	同forEach，回调函数对每个数组元素返回布尔值，全部为true，由every返回true	x
some	ES5	同forEach，回调函数对每个数组元素返回布尔值，若有一个为true则返回true	x
map	ES5	同forEach，回调函数对每个数组元素	x
filter	ES5	同forEach，回调函数返回布尔值，返回结果true的元素组成的新数组	x
reduce②	ES5	同forEach，迭代数组的所有项，并构建一个最终值，由reduce返回	x
join③	-	使用分隔符，将数组转为字符串并返回	x
indexOf	ES5	查询并返回数据的索引	x
lastIndexOf	ES5	反向查询并返回数据的索引	x
reverse	-	反转数组，返回结果	√
sort	-	按照字母顺序对数组排序，支持传入指定的排序方法函数作为参数	√
valueOf④	-	返回对象	x
toString⑤	-	将数组作为字符串返回	x

①
const arr = [1,2];
arr.concat([3,4,5]); //  [1, 2, 3, 4, 5]
arr; // [1,2]

②
// 作用1 求和
const arr = [1,2,3,4,5]
const sum = arr.reduce((result,item) => {console.log(result) // 计算结果console.log(item) // 当前元素return result+item
}, 0)
// 作用2 求数组项最大值
const arr = [1,2,3,4,5]
const sum = arr.reduce((result,item) => {return Math.max(result,item)
})
// 作用3 扁平一个二维数组var arr = [[1, 2, 8], [3, 4, 9], [5, 6, 10]];
var res = arr.reduce((prev, cur) => prev.concat(cur), []);
console.log(res)   // [1,2,8,3,4,9,5,6,10]

③
var a = [1,2,3]
a.join() // '1,2,3'
a.join('-') // '1-2-3'

④
var a = [1,2,3]
a.valueOf() // [1,2,3]

⑤
var a = [1,2,3]
a.toString() // '1,2,3'

迭代器函数