近来打算系统地学习一波数据结构与算法,因此根据LeetCode官方推出地经典面试题目清单开始刷题。本篇文章记录了初级算法中的数组篇,为了追求速度,我先大概地过一遍,每道题没有去分析多种解法,可能不是最优解,仅仅为我做题时的思路,若有什么错误的地方,欢迎大佬们指正哈!
ps:第一次写博客,格式之类的难免有所欠妥,还请大家谅解!
从排序数组中删除重复项
解法:双指针
解析:题中数组是==有序==的,因此重复的值肯定是相邻的,且从第2个值开始才有可能重复,所以遍历数组1~n-1。使用变量cur来作为当前指针,若数组中相邻的值重复,cur保持不变;若数组中出相邻的值不同,则让当前值覆盖cur中的值,cur指向下一个位置。
1 | class Solution { |
时间复杂度:O(n) ,遍历一次数组
空间复杂度:O(1), 需要用到常量空间
买卖股票的最佳时机 II
解法:贪心算法
解析:所有上涨交易日都买卖(赚到所有利润),所有下降交易日都不买卖(永不亏钱)。
1 | class Solution { |
时间复杂度:O(n) ,遍历一次数组
空间复杂度:O(1), 需要用到常量空间
旋转数组
解法:使用反转
解析:这道题要求使用==原地==算法,因此不能开额外的数组。首先要注意的是k的大小,当k大于数组n的长度时,数组每移动n次,就回到了原来的位置,相当于没有改变位置。可以将k对n取模,减少不必要的时间消耗
ps:接下来我开始循环k次,一位一位地移动位置,结果超时了。后面看了官方题解,看到了一种捷径式解法:反转
超时代码:
1 | class Solution { |
时间复杂度:O(k * n) ,遍历k次数组
空间复杂度:O(1), 需要用到常量空间
官方题解:
原始数组 ————- : 1 2 3 4 5 6 7
反转所有数字后 —- : 7 6 5 4 3 2 1
反转前 k 个数字后 - : 5 6 7 4 3 2 1
反转后 n-k 个数字后 : 5 6 7 1 2 3 4 –> 结果
1 | class Solution { |
时间复杂度:O(n) ,反转3次
空间复杂度:O(1), 需要用到常量空间
存在重复
解法:排序+遍历
解析:数组排序后重复值肯定是相邻的,做个简单的遍历判断即可
1 | class Solution { |
时间复杂度:O(n * logn) ,排序的时间复杂度是O(n * logn) ,遍历的时间复杂度是O(n),整个算法的时间复杂度主要由排序决定 。
空间复杂度:O(1), 需要用到常量空间
ps:若想要使用空间换时间消耗的话,可以使用哈希表。
只出现一次的数字
解法:位操作
解析:异或大法好!利用异或的特性(对同一个数异或两次后,相当于没有操作),因此将==初始值设定为零==,只出现一次的数字对0异或,结果即为这个数字的值!!位运算还是挺重要的呀!有时间还是得多练习一下,可以减少很多麻烦
1 | class Solution { |
时间复杂度:O(n) ,遍历一次数组
空间复杂度:O(1), 需要用到常量空间
两个数组的交集
解法:哈希表
解析:建立<int,int>类型的哈希表,将第一个数组的值存放于哈希表中,==键==代表数组元素的值,==值==代表该元素值的数量
1 | class Solution { |
时间复杂度:O(max(n, m)) n是数组一的大小,m是数组二的大小
空间复杂度:O(n), 需要用到常量空间
ps:这道题我没有考虑去进阶,如n远远大于m时,可以为数组二建立哈希表,减少空间消耗,即空间复杂度可以优化为O(min(n, m)),小伙伴们如果有什么好的解法,欢迎在评论区分享emmmm
加一
解法:逆序遍历
解析:对数组进行==原地==修改,从最后一位开始逆序遍历,进行==加一==和==取余==操作,若当前值不为0,即不会产生下一个进位,就直接返回结果。考虑到99999这种连续进位的情况,当遍历整个数组后,还没有返回结果时,则在动态数组的第一位插入进位值1,返回最终结果10…00
1 | class Solution { |
时间复杂度:O(n) ,遍历一次数组
空间复杂度:O(1),原地操作,只需要用到常量空间
移动零
解法:双指针
解析:这道题我的解法与第一道有点类似,使用cur来作为当前指针,并使用cnt来记录当前0的个数
①若存在0,则将nums[i]覆盖为0
②若不存在0,nums[i]即为原始值,cur==i
1 | class Solution { |
时间复杂度:O(n) ,遍历一次数组
空间复杂度:O(1),需要用到常量空间
两数之和
唠叨:作为LeetCode的第一道题,大家应该也是印象深刻吧!想当初因为不太习惯使用vector并且用函数来解决问题,第一道题拖了n久才去提交(还是使用暴力……),很多事情,从0到1,真的是很重要的一个过程了!比如这篇博客,写得一点都不香~
解法:遍历+哈希表
解析:此题我的解法是在遍历过程中判断哈希表中的值,实现一次遍历即可得出结果。==键==代表数组元素的值,==值==为该元素值的下标
1 | class Solution { |
时间复杂度:O(n) ,遍历一次数组
空间复杂度:O(n),哈希表的线性空间复杂度
有效的数独
解法:遍历+哈希表
解析:将大宫格分为9个小的9宫格
建立三个哈希表数组
①行 :i
每次遍历时判断当前行的哈希表是否有相同的数
②列 :j
每次遍历时判断当前列的哈希表是否有相同的数
③宫格:(i / 3) * 3 + (j / 3)
每次遍历时判断当前宫格的哈希表是否有相同的数
借用一下leetcode的分析图:
1 | class Solution { |
时间复杂度:O(1)
空间复杂度:O(1)
ps:这道题的时间复杂度和空间复杂度可能会有一些争议,但是81个单元格和27个map是固定的,也就是常数值,不会随输入的改变而改变
旋转图像
解法:自外向内,顺时针旋转四个值
解析:话不多说,看图
首先是最外一圈,旋转这4个数的值
①15 -> t ②16 -> 15 ③11 -> 16 ④5 -> 11 ⑤ t -> 5
依次类推……
再进入内圈
1 | class Solution { |
时间复杂度:O(n^2),两重循环
空间复杂度:O(1),需要用到常量空间
ps:这道题还有另一种解法,但是相对没有那么容易想到
解法:转置+翻转
解析:转置矩阵(交换matrix[i][j] 和 matrix[j][i]的值),翻转每一行
1 | class Solution { |
时间复杂度:O(n^2),转置和反转都需要用到n的平方
空间复杂度:O(1),需要用到常量空间
总结:
数组类型的问题目前用得比较多的解法是==双指针==、==排序==、==位操作==、==哈希表==和==贪心算法==,还是得具体问题具体分析,因此多实践是很重要的。由于线性代数学得不扎实,一些矩阵的特性不太了解,以后遇到旋转或移动的问题,没有思路的时候可以考虑一下倒置和反转hh。
- 本文作者: a_Gen
- 本文链接: http://imaginee.cn/2020/01/18/LeetCode探索:初级算法(数组篇)/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!