devbox
神奇cpp
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Go语言刷题笔记_go语言实现给定一个正整数及非负整数 nums 的列表,第一个正整数表示nums列表中数

作者：神奇cpp | 2024-07-10 18:29:10

赞

踩

go语言实现给定一个正整数及非负整数 nums 的列表,第一个正整数表示nums列表中数

目录

二分查找

二分查找入门

二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
在这里插入图片描述

func search(nums []int, target int) int {
    low,high := 0, len(nums) - 1 
    for low <= high {
        mid := (low + high) >> 1
        num := nums[mid]
        if num < target {
            low = mid + 1
        }else if num > target {
            high = mid - 1
        }else {
            return mid 
        }
    }
    return -1;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
猜数字大小

猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
返回我选出的数字。

在这里插入图片描述

func guessNumber(n int) int {
    left,right := 0, n
    for left <= right {
        mid := (left + right) >> 1
        if guess(mid) == 0 {
            return mid
        } else if guess(mid) == 1{
            left = mid + 1
        } else {
            right = mid -1 
        }
    }
    return  -1 
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
 func guessNumber(n) int {
 	return sort.Search(n, func(x int) bool { return guess(x) <= 0 })
 }

  • 1
  • 2
  • 3

sort.Search 源码

// Search uses binary search to find and return the smallest index i
// in [0, n) at which f(i) is true, assuming that on the range [0, n),
// f(i) == true implies f(i+1) == true. That is, Search requires that
// f is false for some (possibly empty) prefix of the input range [0, n)
// and then true for the (possibly empty) remainder; Search returns
// the first true index. If there is no such index, Search returns n.
// (Note that the "not found" return value is not -1 as in, for instance,
// strings.Index.)
// Search calls f(i) only for i in the range [0, n).
//
// A common use of Search is to find the index i for a value x in
// a sorted, indexable data structure such as an array or slice.
// In this case, the argument f, typically a closure, captures the value
// to be searched for, and how the data structure is indexed and
// ordered.
func Search(n int, f func(int) bool) int {
	// Define f(-1) == false and f(n) == true.
	// Invariant: f(i-1) == false, f(j) == true.
	i, j := 0, n
	for i < j {
		h := int(uint(i+j) >> 1) // avoid overflow when computing h
		// i ≤ h < j
		if !f(h) {
			i = h + 1 // preserves f(i-1) == false
		} else {
			j = h // preserves f(j) == true
		}
	}
	// i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
	return i
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。
在这里插入图片描述

func searchInsert(nums []int, target int) int {
    l, r := 0, len(nums)-1
    for l <= r{
        mid := (l+r)>>1
        if nums[mid] == target{
            return mid
        }else if nums[mid] < target{
            l = mid + 1
        }else{ //nums[mid] > target
            r = mid - 1
        }
    }
    return l
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
山脉数组的峰顶索引

符合下列属性的数组 arr 称为 山脉数组 ：
arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < … arr[i-1] < arr[i]
arr[i] > arr[i+1] > … > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i 。
在这里插入图片描述在这里插入图片描述

func peakIndexInMountainArray(arr []int) int {
    l, r := 0, len(arr) - 1
    for l < r {
        mid := (r+l)>> 1
        if arr[mid] > arr[mid + 1] {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return r
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
有效的完全平方数

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要 使用任何内置的库函数，如 sqrt 。

在这里插入图片描述

func isPerfectSquare(num int) bool {
	left, right := 0, num
	for left <= right {
		mid := (left + right) >> 1
		square := mid * mid
		if square < num {
			left = mid + 1
		} else if square > num {
			right = mid - 1
		} else {
			return true
		}
	}
	return false
}

func isPerfectSquare1(num int) bool {
	x := int(math.Sqrt(float64(num)))
	return x*x == num
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
两个数组间的距离值

给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。

「距离值」 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。

在这里插入图片描述
在这里插入图片描述

//func findTheDistanceValue(arr1 []int, arr2 []int, d int) int {
//	myabs := func(a, b int) int {
//		if a-b < 0 {
//			return b - a
//		}
//		return a - b
//	}
//	ans := 0
//	for _, v := range arr1 {
//		flag := false
//		for _, vv := range arr2 {
//			if myabs(v, vv) <= d {
//				flag = true
//				break
//			}
//		}
//		if flag == false {
//			ans++
//		}
//	}
//	return ans
//}

func findTheDistanceValue(arr1 []int, arr2 []int, d int) int {
	sort.Ints(arr2)
	ans := 0
	for _, v1 := range arr1 {
		if !binarySearch(arr2, v1, d) {
			ans++
		}
	}
	return ans
}
func binarySearch(arr2 []int, v1, d int) bool {
	myabs := func(a, b int) int {
		if a-b < 0 {
			return b - a
		}
		return a - b
	}
	l := 0
	r := len(arr2) - 1
	for l <= r { //这个边界条件需要考虑l和r相等情况，即arr2长度为1，
		mid := (l + r) >> 1
		if myabs(v1, arr2[mid]) <= d { //绝对值已经够小
			//r = mid
			return true
		}
		//绝对值不够小，较小值需要增加，或者，较大值需要减少
		if v1 > arr2[mid] {
			l = mid + 1
		} else {
			r = mid - 1
		}
	}
	return false
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

在这里插入图片描述

func mySqrt(x int) int {
    left,right := 0,x
    for left <= right {
        mid := (right+left) >> 1
        if mid * mid == x {
            return mid
        }
        if mid * mid > x {
            right = mid -1
        }else {
            left =mid + 1
        } 
    }
    return right
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
寻找比目标字母大的最小字母

给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。

在比较时，字母是依序循环出现的。举个例子：

如果目标字母 target = ‘z’ 并且字符列表为 letters = [‘a’, ‘b’]，则答案返回 ‘a’

在这里插入图片描述

func nextGreatestLetter(letters []byte, target byte) byte {
    left, right := 0, len(letters) - 1
    ans := target
    for left <= right {
        mid := (left +right) / 2
        if letters[mid] > target { 
            ans = letters[mid] 
            right = mid - 1
        }else { 
            left = mid + 1
        }
    }
    if ans == target {
        ans = letters[0]
    }
    return ans
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

在这里插入图片描述

func firstBadVersion(n int) int {
    l,r:=1,n
    for l<r {
        mid :=(l+r) >>1
        if isBadVersion(mid) {
           r=mid     
        } else {
            l=mid+1
        } 
    }
    return l
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

在这里插入图片描述

func searchRange(nums []int, target int) []int {
    l := len(nums)
    if(l==0){
        return []int{-1,-1}
    }
    result := findFirstPos(nums,target)
    if(result == -1){
        return []int{-1,-1}
    }
    return []int{result,findLastPos(nums,target,result)}
}

func findFirstPos(nums []int, target int) int{
    left,right :=0,len(nums)-1
    for left<right {
        mid := (left+right)>>1
        if(nums[mid]<target){
            left = mid + 1
        }else if nums[mid]==target{
            right = mid
        }else{
            right = mid -1
        }
    }
    if nums[left]!=target{
        return -1
    }
    return left
}

func findLastPos(nums []int, target int,left int) int{
    right :=len(nums)-1
    for left<right {
        mid := (left+right+1)>>1
        if nums[mid]<target{
            left = mid + 1
        }else if nums[mid]==target{
            left = mid
        }else{
            right = mid -1
        }
    }
    return right
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
排列硬币

你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。

给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。

在这里插入图片描述

func arrangeCoins(n int) int {
    left := 1
    right := n
    for left <= right {
        mid := (left + right) >>1 
        cnt := (1 + mid) * mid >> 1
        if cnt == n {
            return mid
        } else if cnt < n {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return right
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
第 k 个缺失的正整数

给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。

请你找到这个数组里第 k 个缺失的正整数。
在这里插入图片描述

// 思路与算法
// 对于每个元素 ai，我们都可以唯一确定到第 i 个元素为止缺失的元素数量为 ai−i−1，例如:

//     第 i 个元素	ai的值	到第 i 个元素为止缺失的元素数量 pi
// a0   2	                1
// a1   3	                1
// a2   4                  1
// a3   7	                3
// a4   11	                6
// 我们发现 pi 是随 i 非严格递增的，于是可以使用二分查找解决这个问题。我们只要找到一个 i 使得 p(i−1)<k≤pi，就可以确定缺失的第 k 个数为 k−p(i−1)+a(i−1)。也就是说，我们要找到第一个大于等于 k 的 pi。

// 在实现的时候，我们要注意两个边界的处理：
// 当 a0>k 时，最终 i=0，找不到 i−1，所以提前判断是否 a0>k，如果是，则直接返回 k。
// 当最后一个元素对应的缺失个数 p(n−1)<k 时，我们并不能找到第一个大于等于 k 的 pi，为了解决这个问题，可以在 a 序列的最后加入一个虚拟的值，这个值的大小为一个不会出现的非常大的数，这样就可以保证一定能找到一个大于等于 k 的 pi。

func findKthPositive(arr []int, k int) int {
	if arr[0] > k {
		return k
	}
    n := len(arr)
	l, r := 0, n-1
	if arr[r]-r-1 < k { //截止到arr最后一个元素，缺失的元素数量仍小于k
		return r + 1 + k
	}
    best := n-1
	for l <= r {
		mid := (l + r) / 2
		if arr[mid]-mid-1 >= k {//截止到arr的mid下标元素，缺失的元素数量大于等于k
            best=mid
			r = mid-1
		} else {
			l = mid+1
		}
	}
	return best+k
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
特殊数组的特征值

给你一个非负整数数组 nums 。如果存在一个数 x ，使得 nums 中恰好有 x 个元素 大于或者等于 x ，那么就称 nums 是一个 特殊数组 ，而 x 是该数组的 特征值 。

注意： x 不必 是 nums 的中的元素。

如果数组 nums 是一个 特殊数组 ，请返回它的特征值 x 。否则，返回 -1 。可以证明的是，如果 nums 是特殊数组，那么其特征值 x 是 唯一的 。
在这里插入图片描述
在这里插入图片描述

func specialArray(nums []int) int {
    sort.Ints(nums)
    for i := 0; i <= nums[len(nums) - 1]; i++ {
        left, right := 0, len(nums) - 1
        for left < right {
            mid := (left + right) >> 1
            if nums[mid] < i {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        cnt := len(nums) - left - 1
        if nums[left] >= i {
            cnt++
        }
        if cnt == i {
            return i
        }
    }
    return -1
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。
在这里插入图片描述

func twoSum(numbers []int, target int) []int {
    for i := 0; i < len(numbers); i++ {
        low, high := i + 1, len(numbers) - 1
        for low <= high {
            mid := (high+ low)>> 1
            if numbers[mid] == target - numbers[i] {
                return []int{i + 1, mid + 1}
            } else if numbers[mid] > target - numbers[i] {
                high = mid - 1
            } else {
                low = mid + 1
            }
        }
    }
    return []int{-1, -1}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
统计有序矩阵中的负数

给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。 请你统计并返回 grid 中 负数 的数目。
在这里插入图片描述

func countNegatives(grid [][]int) int {
	var res int
	for _, nums := range grid {
		res += binary(nums)
	}
	return res
}

func binary(nums []int) int {
	left, right := 0, len(nums)
	for left < right {
		mid := (left + right) >> 1
		if nums[mid] >= 0 {
			left++
		} else {
			if mid == 0 || nums[mid-1] >= 0 {
				return len(nums) - mid
			}
			right--
		}
	}
	return 0
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

在这里插入图片描述
在这里插入图片描述

func searchMatrix(matrix [][]int, target int) bool {
    row := sort.Search(len(matrix), func(i int) bool { return matrix[i][0] > target }) - 1
    if row < 0 {
        return false
    }
    col := sort.SearchInts(matrix[row], target)
    return col < len(matrix[row]) && matrix[row][col] == target
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
矩阵中战斗力最弱的 K 行

给你一个大小为 m * n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。

请你返回矩阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。

如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。

军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。

在这里插入图片描述
在这里插入图片描述

func kWeakestRows(mat [][]int, k int) []int {
    l1 := make([]int, len(mat))
    l2 := make([]int, len(mat))
    for i := 0; i < len(mat); i++ {
        l1[i] = i
        j := len(mat[0])-1
        for j >= 0 {
            if mat[i][j] == 1 {
                l2[i] = j+1
                break
            }
            j--
        }
        if j < 0 {
            l2[i] = 0
        }
    }
    for i := 0; i < len(l1); i++ {
        for j := 0; j < len(l1)-1; j++ {
            if l2[j] > l2[j+1] {
                l2[j], l2[j+1] = l2[j+1], l2[j]
                l1[j], l1[j+1] = l1[j+1], l1[j]
            }
        }
    }
    return l1[:k]
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
检查整数及其两倍数是否存在

给你一个整数数组 arr，请你检查是否存在两个整数 N 和 M，满足 N 是 M 的两倍（即，N = 2 * M）。

更正式地，检查是否存在两个下标 i 和 j 满足：

i != j
0 <= i, j < arr.length
arr[i] == 2 * arr[j]

在这里插入图片描述

func checkIfExist(arr []int) bool {
    // 排序
    sort.Ints(arr)
    for i, v := range arr {
        left, right := 0, len(arr) - 1
        for left <= right {
            mid := (right + left) >> 1 
            if arr[mid] >= v * 2 {
                right = mid - 1
            } else {
                left = left + 1
            }
        }     
        if left < len(arr) && arr[left] == v * 2 && left != i {
            return true
        }
    }
    return false
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

在这里插入图片描述

func intersect(nums1 []int, nums2 []int) []int {
    i,j,k := 0,0,0
    sort.Ints(nums1)
    sort.Ints(nums2)
    for i < len(nums1) && j < len(nums2){
        if nums1[i] < nums2[j]{
            i++
        }else if nums1[i] > nums2[j]{
            j++
        }else{
            nums1[k] = nums1[i]
            k++
            i++
            j++
        }
    }
    return nums1[:k]
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
平方数之和

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

在这里插入图片描述

func judgeSquareSum(c int) bool {
    left, right := 0, int(math.Sqrt(float64(c)))
    for left <= right {
        sum := left*left + right*right
        if sum == c {
            return true
        } else if sum > c {
            right--
        } else {
            left++
        }
    }
    return false
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
下标对中的最大距离

给你两个 非递增 的整数数组 nums1​​​​​​ 和 nums2​​​​​​ ，数组下标均 从 0 开始 计数。

下标对 (i, j) 中 0 <= i < nums1.length 且 0 <= j < nums2.length 。如果该下标对同时满足 i <= j 且 nums1[i] <= nums2[j] ，则称之为 有效 下标对，该下标对的 距离 为 j - i​​ 。​​

返回所有 有效 下标对 (i, j) 中的 最大距离 。如果不存在有效下标对，返回 0 。

一个数组 arr ，如果每个 1 <= i < arr.length 均有 arr[i-1] >= arr[i] 成立，那么该数组是一个 非递增 数组。

在这里插入图片描述

func maxDistance(nums1 []int, nums2 []int) int {
	n1, n2 := len(nums1), len(nums2)
	i := 0
	ans := 0
	for j := 0; j < n2; j++ {
		for i < n1 && nums1[i] > nums2[j] {
			i++
		}
		if i < n1 && j-i > ans {
			ans = j - i
		}
	}
	return ans
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
在这里插入图片描述

func search(nums []int, target int) int {
	l, r := 0, len(nums)-1
	for l <= r {
		mid := (l + r)>>1
		if nums[mid] == target {
			return mid
		}
		// l, mid, r 一条线
		if nums[mid] >= nums[l] && nums[mid] <= nums[r] {
			if target < nums[mid] {
				r = mid - 1
			} else {
				l = mid + 1
			}
		} else if nums[mid] >= nums[l] { // l, mid在左， r在右
			if target > nums[mid] || target < nums[l] {
				l = mid + 1
			} else {
				r = mid - 1
			}
		} else { // l在左，mid, r在右
			if target < nums[mid] || target >= nums[l] {
				r = mid - 1
			} else {
				l = mid + 1
			}
		}
	}
	return -1
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
在这里插入图片描述

func findMin(nums []int) int {
    low, high := 0, len(nums) - 1
    for low < high {
        mid :=(low +high) >> 1
        if nums[mid] < nums[high] {
            high = mid
        } else {
            low = mid + 1
        }
    }
    return nums[low]
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/神奇cpp/article/detail/807199
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号