【golang】leetcode初级-合并两个有序数组&第一个错误版本
第一题 合并两个有序数组
题目信息
文章图片
、
解题思路
由题可知，我们需要将第二个数组的元素合并到第一个数组之后返回
两个数组都是有序的，因此对于每个想要插入数组的元素，我们只要找到首个大于这个元素的数，将其插入到这个数的前方即可
代码
func merge(nums1 []int, m int, nums2 []int, n int){
k:=0
for i:=0;
i复杂度分析
时间复杂度：O（m+n）执行的循环次数为数组二的个数n，也就是插入数组一的元素个数，再加上指针搜索插入位置的移动长度，最坏情况等于数组一的长度m
空间复杂度：O（1），常数次空间
另一种解法
文章图片
此方案减少了插入时的复制元素数量，效率得到了一定的提升
第二题 第一个错误的版本 题目信息
文章图片
解题思路
尽量减少调用的次数
显然二分查找能最快的定位到第一个错误版本
每次将n个版本一分为二 取中间n/2的版本
如果他是正确的版本，那么显然前面的部分都是正确的，错误的版本就在后面的一半中
如果他的错误的版本，那么显然后面的部分都是错误的，正确的版本就在前面的一半中
继续进行二分搜索，直到长度为一，那么他就是第一个错误的版本
二分查找适用于有序的查找定位，能将O（n）的时间复杂度降低到O（logn）
代码
func firstBadVersion(n int) int {
first:=1
var mid int
mid=(first+n)/2
for mid!=first{
if isBadVersion(mid){
n=mid
mid=(first+n)/2
}else {
first = mid
mid = (first + n) / 2
}
}
if isBadVersion(mid){return mid}
return mid+1}
官解
文章图片
调用了sort包的search函数
search函数的源码如下
文章图片
复杂度分析
复杂度分析
时间复杂度：O(logn)，其中 n 是给定版本的数量。
【【golang】leetcode初级-合并两个有序数组&第一个错误版本】空间复杂度：O(1)。我们只需要常数的空间保存若干变量。
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长