【golang】leetcode初级-合并两个有序数组&第一个错误版本

第一题合并两个有序数组

题目信息

【golang】leetcode初级-合并两个有序数组&第一个错误版本、

解题思路

由题可知，我们需要将第二个数组的元素合并到第一个数组之后返回

两个数组都是有序的，因此对于每个想要插入数组的元素，我们只要找到首个大于这个元素的数，将其插入到这个数的前方即可

代码

func merge(nums1 []int, m int, nums2 []int, n int)  {
    k:=0
    for i:=0;i<n;i++{
        for nums1[k]<=nums2[i]{
            if(k==m) {break}
            k++
        }
        copy(nums1[k+1:m+1],nums1[k:m])
        m++
        nums1[k]=nums2[i]
    }
}

复杂度分析

时间复杂度：O（m+n）执行的循环次数为数组二的个数n，也就是插入数组一的元素个数，再加上指针搜索插入位置的移动长度，最坏情况等于数组一的长度m
空间复杂度：O（1），常数次空间

另一种解法

【golang】leetcode初级-合并两个有序数组&第一个错误版本
此方案减少了插入时的复制元素数量，效率得到了一定的提升

第二题第一个错误的版本

题目信息

【golang】leetcode初级-合并两个有序数组&第一个错误版本

解题思路

尽量减少调用的次数
显然二分查找能最快的定位到第一个错误版本
每次将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

}