关于golang:golangleetcode中级搜索旋转排序数组搜索二维矩阵Ⅱ

第一题 搜寻旋转排序数组

题目

解题思路

代码

func search(nums []int, target int) int {
    //初始化边界和二分搜寻的中点
    l := 0
    r := len(nums) - 1
    var mid int

    for l <= r{ 
        //取中点，如果中点为指标则间接返回
        mid = l + (r - l) / 2
        if target == nums[mid]{
            return mid
        }

        //mid至多会有一端有序，能够利用有序段膨胀边界。
        if nums[mid] >= nums[l] {//左端有序
            if target < nums[mid] && target >= nums[l] { //元素在左端
                    r = mid - 1
                }else{ //排除左端
                    l = mid + 1
                }
            }else{//右端有序
                if target > nums[mid] && target <= nums[r] { //元素在右端
                    l = mid + 1
                }else{ //排除右端
                    r = mid - 1
                }
            }
    }
    return -1
}

复杂度剖析

工夫复杂度： O(logn)，其中 n 为 nums 数组的大小。整个算法工夫复杂度即为二分查找的工夫复杂度 O(logn)。

空间复杂度： O(1) 。咱们只须要常数级别的空间寄存变量。

第二题 搜寻二维矩阵Ⅱ

题目

思路

对于二维矩阵，咱们能够把它看作为多个数组的聚合

且矩阵的行和列都是升序排列的

因而咱们只需搜寻行首元素小于等于terget的行

并且
搜寻行能够间接应用上一题所提供的函数

代码

func searchMatrix(matrix [][]int, target int) bool {
    for _,v:=range matrix {
        if v[0]==target{return true}
        if v[0]<target{if search(v,target)!=-1 {return true}}
    }
    return false
}
func search(nums []int, target int) int {
    //初始化边界和二分搜寻的中点
    l := 0
    r := len(nums) - 1
    var mid int

    for l <= r{
        //取中点，如果中点为指标则间接返回
        mid = l + (r - l) / 2
        if target == nums[mid]{
            return mid
        }

        //mid至多会有一端有序，能够利用有序段膨胀边界。
        if nums[mid] >= nums[l] {//左端有序
            if target < nums[mid] && target >= nums[l] { //元素在左端
                r = mid - 1
            }else{ //排除左端
                l = mid + 1
            }
        }else{//右端有序
            if target > nums[mid] && target <= nums[r] { //元素在右端
                l = mid + 1
            }else{ //排除右端
                r = mid - 1
            }
        }
    }
    return -1
}

成果

复杂度剖析

工夫复杂度： O(nlogn)，其中 n 为 matrix 矩阵的长度。每一行的工夫复杂度即为二分查找的工夫复杂度 O(logn)， 最多须要搜寻n行

空间复杂度： O(1) 。咱们只须要常数级别的空间寄存变量。

优化

func searchMatrix(matrix [][]int, target int) bool {
    m, n := len(matrix), len(matrix[0])
    x, y := 0, n-1
    for x < m && y >= 0 {
        if matrix[x][y] == target {
            return true
        }
        if matrix[x][y] > target {
            y--
        } else {
            x++
        }
    }
    return false
}


作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/solution/sou-suo-er-wei-ju-zhen-ii-by-leetcode-so-9hcx/
起源：力扣（LeetCode）
著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。

成果