乐趣区

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

jiezi

第一题 搜寻旋转排序数组

题目

解题思路


代码

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）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。

成果

退出移动版