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

48次阅读

共计 887 个字符,预计需要花费 3 分钟才能阅读完成。

第一题 合并两个有序数组

题目信息

解题思路

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

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

代码

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)。咱们只须要常数的空间保留若干变量。

正文完
 0