乐趣区

关于leetcode个人解题总结:golangleetcode初级合并两个有序数组第一个错误版本

jiezi

第一题 合并两个有序数组

题目信息

、

解题思路

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

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

代码

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），常数次空间

另一种解法


此计划缩小了插入时的复制元素数量，效率失去了肯定的晋升

第二题 第一个谬误的版本

题目信息

解题思路

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

空间复杂度：O(1)。咱们只须要常数的空间保留若干变量。

退出移动版