什么叫ARTS?
每周完成一个ARTS:
- Algorithm:每周至少做一个 leetcode 的算法题
- Review:阅读并点评至少一篇英文技术文章
- Tip:学习至少一个技术技巧
- Share:分享一篇有观点和思考的技术文章
作者:陈皓
链接:https://www.zhihu.com/question/301150832/answer/529809529
来源:知乎
_Merge Sorted Array
给两个有序数组排序,排序后合并到数组1中。
1 | Input: |
方法一
- 采用双指针法,同时遍历两个数组。
- 比较遍历到的数,将较小的数提取到临时数组,临时指针++,较小数组遍历指针++,如果相等,将这个等数提取到临时数组,需要存两次,同时两个数组的遍历指针++。
- 直到有一方遍历完成,将另外未遍历完的直接插入临时数组。
1 | class Solution { |
方法二
- 排完序的数组1总共有m+n位,从两数组末尾m,n处同时遍历数组,将大的数存入数组1的m+n末尾,大的数存入后还需要移动指针,相等的数需要存入两次,两个数组的指针都需要移动一次。
- 遍历完成,再将剩下未遍历完的数组补上到数组1的末尾。
1 | class Solution { |
First Bad Version
找到第一个坏版本
1 | Given n = 5, and version = 4 is the first bad version. |
方法一
- 采用折半查找,先找一半的那个数是否是坏版本,如果不是则向前找一半,如果是,则向后找一半。折半查找的方法为定义一个low,high,不断缩减范围,注意跳出循环的条件。
- 直到无法寻找。
1 | // Forward declaration of isBadVersion API. |