数组的基本概念
定义:
- 通常由一组相同类型的元素的集合所组成的结构(javascript允许数组中包含不同类型的元素)
- 计算机会分配一块连续的内存来存储这个元素集合
- 利用索引可以取出元素对应的存储地址
特性:
- 在内存中为连续空间
定址公式:addr(curElem)=addr(intialElem)+sizeof(curElem)*index - 通过index获取数组元素的时间复杂度为O(1)
- 通常数组第一个位置的索引是0
数组示意图如下:
在java中可以这么定义一个数组
int[] array = {2,4,5,6,22,89,35} //定义数组
array[1] // 值为4 取出索引1位置的值
array[5] // 值为89 取出索引5位置的值
我们还可以定义二维数组
int[][] array={{1,2,3},{66,45,33,4},{2,7,8}}
三维数组也是可以定义的, 这里就不举例了
为什么使用数组
- 简化代码, 提高效率
- 将相同类型的元素组织在一起
比如, 我们要存1-1000这1000个数, 用数组就能很简单的存储, 并且由于数组的每一个元素都是连续开辟的内存空间, 所以也能快速的取到中间任意的值
int[] nums = new int[1000];
for(int i=0; i<nums.length;i++) {
nums[i] = i+1;
}
nums[5] //6
nums[926] //927
常见数组算法题
因为我自己比较熟悉js, 所以关于算法题的代码, 我都用js代码写, 当然我也只是个初学者, 所以大家不要纠结我代码写的好不好看, 主要看解题思路就好了
例1: 两数之和
给定一个整数数组(无重复元素)和一个目标值, 找出数组中和为目标值的两个数。
按照从小到大的顺序输出结果对
将所有结果对输出到一个数组
例:
Input: number = {2,7,11,15}, target = 9
Output: {2,7}
分析需求:
- 数组是否排序
- 有没有重复元素
- 结果是返回全部还是返回任意一个
解题思路:
思路1：
暴力解法来解
function twoSum(arr, target) {
let result = []
let index = 0
if(arr.length < 2) {
return result
}
for(let i=0; i<arr.length; i++) {
for(let j=i+1; j<arr.length; j++) {
if(arr[i] + arr[j] === target) {
if(arr[i] < arr[j]) {
result[index] = []
result[index].push(arr[i])
result[index].push(arr[j])
index++
}else {
result[index] = []
result[index].push(arr[j])
result[index].push(arr[i])
index++
}
}
}
}
return result
}
let newArray = twoSum([1,3,4,5,6,8,78], 9)
console.log(newArray)
思路1总结:
- 时间复杂度O(n2)
- 存在无意义操作
例如:
78已经大于9了, 所以每次对它操作都是在浪费时间
思路2:
排序+两根指针
这里由于我们还没有讲到排序, 所以对于排序我们直接用js里面提供的sort方法, 如果大家以后面试的话, 除非是考官强制要求不能使用api, 否则能用编程语言提供的api, 我们一定要使用语言自带的api, 这样能节省很多时间
两根指针的方法在面试中是一个很实用的方法
- 通过对数组排序与两个指针组合, 减少无意义的遍历
- 两根指针: 一根指针(start)指向数组的第一个元素(数组中最小元素), 另一个指针(end)指向数组最后一个元素(数组中最大元素)
- 核心思想: 如果现在两根指针所指元素之和大于目标值, 则表明现在两数之和过大, 应使end指针指向更小的数, 即索引减小(end--), 反之则表明现在两数之和过小, 应使start指针指向更大的数, 即索引增加(start++)
function sum(arr, target) {
let start = 0
let end = arr.length-1
let result = []
let index = 0
if(arr.length < 2) {
return result
}
arr.sort((x,y) => {
return x-y
})
while(start < end) {
if(arr[start] + arr[end] > target) {
end--
continue
}else if(arr[start] + arr[end] < target) {
start++
continue
}else if(arr[start] + arr[end] === target) {
result[index] = []
result[index].push(arr[start])
result[index].push(arr[end])
start++
index++
continue
}
}
return result
}
思路2总结:
- 通过对数组排序与两根指针组合, 减少无意义的遍历
- 使用两个指针(而不是一个)以相同/相反的方向遍历数组
- 时间复杂度分析: 排序: O(nlogn), 两根指针算法: O(n)
时间复杂度: O(nlogn) + O(n) => O(nlogn)
例2: 三数之和
给定一个包含n个整数的数组(无重复元素)和一个目标值, 找出数组中和为目标值的三个数
例如:
给定一个数组nums = [-1, 0 ,1, 2, -5, 3], target = 0
满足要求的三元组集合为:[[-1,0,1], [2,-5,3]]
思路1:
- 暴力解法
算法复杂度: O(n3)
注意: 面试的时候这种算法基本上不用写了, 太蠢了, 最多可以当成你思路的第一步告诉面试官 - 尝试用排序+两根指针算法
- 遍历第一个数字num1, 看看另外两个数之和是否能满足target - num1, 这就转化成两数之和的问题了
- 时间复杂度: 排序O(nlogn), 两数之和: O(n2)
O(nlogn) + O(n2) => O(n2)
function sum(arr, target) {
let result = []
let first
let second = arr.length - 1
let index = 0
if(arr.length < 3) {
return result
}
arr.sort((x,y) => {
return x-y
})
for(let i=0; i<arr.length; i++ ) {
first = i+1
while(first < second) {
if(arr[first] + arr[second] > target - arr[i]) {
second--
continue
}else if(arr[first] + arr[second] < target - arr[i]){
first++
continue
}else if(arr[first] + arr[second] === target - arr[i]) {
result[index] = []
result[index].push(arr[i])
result[index].push(arr[first])
result[index].push(arr[second])
first++
index++
continue
}
}
}
return result
}
K-sum解法总结
- 排序
- 尝试遍历第一个数, 将问题转化成(K-1)Sum, 以此类推
- 时间复杂度
2-Sum: O(nlogn) + O(nlogn) => O(nlogn)
3-Sum: O(nlogn) + O(n2) => O(n2)
4--Sum: O(nlogn) + O(3) => O(n3
5-Sum: O(nlogn) + O(n(k-1)) => O(n(k-1))
例3: 反转数组
给定一个数组, 反转数组中的所有数字
例:
Input: {1,2,88,45,3,7}
Output: {7,3,45,88,2,1}
分析:
- 数组是否合法
- 数组是否已经排序
- 数组是否有重复元素
这到底就很简单了
- 用双指针, fisrt指向数组的第一个, end指向数组的最后一个
- 交换arr[first]和arr[end]的值.然后指针first++往后移一位, 同时end--往前移一位
- 直到first >= end(指针first和end相遇, 即表示整个数组已经遍历完), 结束交换
function reverse(arr) {
let first = 0
let end = arr.length - 1
while(first < end) {
[arr[first], arr[end]] = [arr[end], arr[first]]
first++
end--
}
return arr
}
算法复杂度: O(n)
例4: 奇数偶数排序
给定一组数组, 对它们进行排序, 以便所有奇数整数在偶数整数之前出现。元素顺序可以改变。排序的奇数和偶数的顺序无关紧要。
例:
Input:{4,3,5,2,1,11,0,8,6,9}
Output:{9,3,5,11,1,2,0,8,6,4}
思路:
- 第一步先用暴力解法:
额外开辟两个数组, 一个数组存储奇数, 一个数组存储偶数, 然后依次先把奇数输出, 再把偶数输出到另外一个新数组, 这种解法时间复杂度为O(n), 但是要另外开辟三个新数组, 所以要浪费额外空间复杂度O(n) - 用双指针
- 跟之前所有套路一样, first指向数组第一个, end指向数组最后一个
- 从数组的第一个开始判断, 如果是奇数, 则first++,指向数组的下一个元素,继续判断, 直到遇到偶数,指针first记录偶数的位置。 这时候从数组的最后一个开始判断, 如果是偶数, 则end--, 指针指向数组前一个元素, 继续判断, 直到遇到奇数, end记录奇数的位置。交换first位置和end位置的两个数
- 交换完成后, 按照第二步的方法继续往后判断, 知道firt指针和end指针相遇(first >= end), 就完成了排序
function swap(arr) {
let first = 0
let end = arr.length-1
while(first < end) {
while(first < end && arr[first] % 2 === 1) {
first++
}
while(first < end && arr[end] % 2 === 0) {
end--
}
[arr[first],arr[end]] = [arr[end], arr[first]]
first++
end--
}
return arr
}
总结:
- 因为这个算法只遍历了一遍数组, 所以时间复杂度: O(n)
- 没有开辟额外的内存空间, 所以空间复杂度: O(1)
- 相比暴力算法时间复杂度是一样的, 但是节省了空间
例5: 合并两个有序数组
给定两个有序整数数组, 按照递增顺序将他们合并到一个排序数组中
Input: {1,3,5}, {2,4,6}
Output: {1,2,3,4,5,6}
分析:
- 数组是否已排序
- 数组是否有重复
- 返回什么数据
思路:
- 同样用双指针, 但是这次不太一样, 这次的双指针分别指向两个数组, 并且指针移动方向相同
- 开辟一个新数组保存排序后的数组, 数组长度为两个待排序数组长度之和
- 两个数组都从第一个开始遍历， 从第一个位置开始比较两个数组元素的值, 值比较小的那个元素输入到新开辟的数组中的第一个位置, 然后小值所在的数组索引+1, 大值得数组索引不变
- 拿之前小值所在的数组位置1的元素跟大值数组位置0的做对比, 跟上面上一样, 哪个值小, 他所在的数组索引值就+1, 值大的那个数组索引不变, 继续比直到其中一个数组所有元素都遍历完了
- 当一个数组所有的值遍历完, 另一个数组还没有遍历完时, 将没有遍历完的数组剩下的值依次输入到新数组中余下的位置
- 新数组中的元素就是排序结果
function merge(arr1, arr2) {
let mergeArr = new Array(arr1.length + arr2.length)
let [index,index1,index2] = [0,0,0]
while(index1 < arr1.length && index2 < arr2.length) {
if(arr1[index1] <= arr2[index2]) {
mergeArr[index] = arr1[index1]
index1++
index++
}else if(arr1[index1] > arr2[index2]) {
mergeArr[index] = arr2[index2]
index2++
index++
}
}
for(let i = index1; i<arr1.length; i++) {
mergeArr[index] = arr1[i]
index++
}
for(let i = index2; i<arr1.length; i++) {
mergeArr[index] = arr2[i]
index++
}
return mergeArr
}
总结:
- 时间复杂度: 因为分别需要遍历两个数组, 所以为O(m+n)
- 空间复杂度: 开辟了新的数组用来保存排序后的结果, 所以额外空间复杂度为O(m+n),
这个空间是必须开辟的, 所以这并不算浪费空间
关于数组我们就说到这里, 请大家期待下次的更新吧.
