LeetCode Go · 二分查找（1）

返回题库与筛选 · 收录范围与使用说明

来源与许可

题目版权归 LeetCode；题解来自 Doocs/leetcode，按 CC BY-SA 4.0 共享。补充 Go 代码来自灵茶山艾府、halfrost，保留 MIT 许可及逐题署名。本站提取 Go、调整分类及折叠排版；标注“本站整理”的 Go 解法依据题意与参考思路补写，按 CC BY-SA 4.0 共享。收录日期：2026-10-31；主题源版本：91ef8c241a5e。

本卷 30 题 · 点击题目展开，先独立思考，再查看解法。

4. 寻找两个正序数组的中位数

困难1 种解法

标签：数组、二分查找、分治

题目、示例与约束

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

 

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

 

 

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

方法一：分治 · Go 实现

思考

若将两个有序数组合并后再取中位数，时间复杂度为 $O(m+n)$。在 $m,n\le {10}^3$ 的范围内可以接受，但题目要求 $O(\log (m+n))$，因此不能线性扫描。

注意到中位数只取决于合并后正中间的一两个位置，比它更小的元素只需知道个数，而不必真正列出。两数组均有序，比较各自第 $\lfloor k/2\rfloor$ 个数，即可判断其中一侧的前一半不可能是第 $k$ 小，从而一次排除一半候选。

因此我们在剩余区间上求第 $k$ 小，而不构造合并数组。将中位数统一为第 $\lfloor (m+n+1)/2\rfloor$ 与第 $\lfloor (m+n+2)/2\rfloor$ 个数的平均，奇数与偶数长度可以共用同一套逻辑。若某一侧不足 $\lfloor k/2\rfloor$ 个元素，则将该侧视为 $+\mathrm{\infty }$，只会排除另一侧。

题目要求算法的时间复杂度为 $O(\log (m+n))$，因此不能直接遍历两个数组，而是需要使用二分查找的方法。

如果 $m+n$ 是奇数，那么中位数就是第 $\lfloor \frac{m+n+1}{2}\rfloor$ 个数；如果 $m+n$ 是偶数，那么中位数就是第 $\lfloor \frac{m+n+1}{2}\rfloor$ 和第 $\lfloor \frac{m+n+2}{2}\rfloor$ 个数的平均数。实际上，我们可以统一为求第 $\lfloor \frac{m+n+1}{2}\rfloor$ 个数和第 $\lfloor \frac{m+n+2}{2}\rfloor$ 个数的平均数。

因此，我们可以设计一个函数 $f(i,j,k)$，表示在数组 $nums1$ 的区间 $[i,m)$ 和数组 $nums2$ 的区间 $[j,n)$ 中，求第 $k$ 小的数。那么中位数就是 $f(0,0,\lfloor \frac{m+n+1}{2}\rfloor )$ 和 $f(0,0,\lfloor \frac{m+n+2}{2}\rfloor )$ 的平均数。

函数 $f(i,j,k)$ 的实现思路如下：

• 如果 $i\ge m$，说明数组 $nums1$ 的区间 $[i,m)$ 为空，因此直接返回 $nums2[j+k-1]$；
• 如果 $j\ge n$，说明数组 $nums2$ 的区间 $[j,n)$ 为空，因此直接返回 $nums1[i+k-1]$；
• 如果 $k=1$，说明要找第一个数，因此只需要返回 $nums1[i]$ 和 $nums2[j]$ 中的最小值；
• 否则，我们分别在两个数组中查找第 $\lfloor \frac{k}{2}\rfloor$ 个数，设为 $x$ 和 $y$。（注意，如果某个数组不存在第 $\lfloor \frac{k}{2}\rfloor$ 个数，那么我们将第 $\lfloor \frac{k}{2}\rfloor$ 个数视为 $+\mathrm{\infty }$。）比较 $x$ 和 $y$ 的大小：
  • 如果 $x\le y$，则说明数组 $nums1$ 的第 $\lfloor \frac{k}{2}\rfloor$ 个数不可能是第 $k$ 小的数，因此我们可以排除数组 $nums1$ 的区间 $[i,i+\lfloor \frac{k}{2}\rfloor )$，递归调用 $f(i+\lfloor \frac{k}{2}\rfloor ,j,k-\lfloor \frac{k}{2}\rfloor )$。
  • 如果 $x>y$，则说明数组 $nums2$ 的第 $\lfloor \frac{k}{2}\rfloor$ 个数不可能是第 $k$ 小的数，因此我们可以排除数组 $nums2$ 的区间 $[j,j+\lfloor \frac{k}{2}\rfloor )$，递归调用 $f(i,j+\lfloor \frac{k}{2}\rfloor ,k-\lfloor \frac{k}{2}\rfloor )$。

时间复杂度 $O(\log (m+n))$，空间复杂度 $O(\log (m+n))$。其中 $m$ 和 $n$ 分别是数组 $nums1$ 和 $nums2$ 的长度。

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	m, n := len(nums1), len(nums2)
	var f func(i, j, k int) int
	f = func(i, j, k int) int {
		if i >= m {
			return nums2[j+k-1]
		}
		if j >= n {
			return nums1[i+k-1]
		}
		if k == 1 {
			return min(nums1[i], nums2[j])
		}
		p := k / 2
		x, y := 1<<30, 1<<30
		if ni := i + p - 1; ni < m {
			x = nums1[ni]
		}
		if nj := j + p - 1; nj < n {
			y = nums2[nj]
		}
		if x < y {
			return f(i+p, j, k-p)
		}
		return f(i, j+p, k-p)
	}
	a, b := f(0, 0, (m+n+1)/2), f(0, 0, (m+n+2)/2)
	return float64(a+b) / 2.0
}

力扣原题 · Doocs 题解来源

33. 搜索旋转排序数组

中等1 种解法

标签：数组、二分查找

题目、示例与约束

整数数组 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 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

 

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

输入：nums = [1], target = 0
输出：-1

 

提示：

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -104 <= target <= 104

方法一：二分查找 · Go 实现

思考

线性扫描的时间复杂度为 $O(n)$。题目要求 $O(\log n)$，因此不能逐个比较。

数组被旋转后整体不再有序，普通二分无法直接判断 $target$ 落在哪一半。

注意到，任取中点将区间一分为二，其中至少有一半保持单调。比较 $nums[0]$ 与 $nums[mid]$ 即可判断左半是否有序；若 $target$ 落在该有序区间内，则丢弃另一半，否则在无序半段中继续查找。因此仍可二分：有序半段用来判定去留，无序半段留给下一轮继续分割。

我们使用二分，将数组分割成 $[left,..mid]$, $[mid+1,..right]$ 两部分，这时候可以发现，其中有一部分一定是有序的。

因此，我们可以根据有序的那一部分，判断 $target$ 是否在这一部分中：

• 若 $[0,..mid]$ 范围内的元素构成有序数组：
  • 若满足 $nums[0]\le target\le nums[mid]$，那么我们搜索范围可以缩小为 $[left,..mid]$；
  • 否则，在 $[mid+1,..right]$ 中查找；
• 若 $[mid+1,n-1]$ 范围内的元素构成有序数组：
  • 若满足 $nums[mid]<target\le nums[n-1]$，那么我们搜索范围可以缩小为 $[mid+1,..right]$；
  • 否则，在 $[left,..mid]$ 中查找。

二分查找终止条件是 $left\ge right$，若结束后发现 $nums[left]$ 与 $target$ 不等，说明数组中不存在值为 $target$ 的元素，返回 $-1$，否则返回下标 $left$。

时间复杂度 $O(\log n)$，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(1)$。

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

力扣原题 · Doocs 题解来源

34. 在排序数组中查找元素的第一个和最后一个位置

中等1 种解法

标签：数组、二分查找

题目、示例与约束

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

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

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

 

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

 

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

方法一：二分查找 · Go 实现

思考

扫描一遍记下 $target$ 的首次与末次出现，时间复杂度为 $O(n)$。 $n\le {10}^5$ 且题目要求 $O(\log n)$；即便先找到一个命中再向两侧扩展，最坏仍是线性。

数组非递减，左右边界各自是一个二分问题，不必在同一轮里同时寻找两端。左边界即第一个不小于 $target$ 的位置，右边界即第一个不小于 $target+1$ 的位置减一。两次下界查找即可；若两次结果相同，说明 $target$ 不存在。

我们可以进行两次二分查找，分别查找出左边界和右边界。

时间复杂度 $O(\log n)$，其中 $n$ 是数组 $\mathit{\text{nums}}$ 的长度。空间复杂度 $O(1)$。

func searchRange(nums []int, target int) []int {
	l := sort.SearchInts(nums, target)
	r := sort.SearchInts(nums, target+1)
	if l == r {
		return []int{-1, -1}
	}
	return []int{l, r - 1}
}

力扣原题 · Doocs 题解来源

35. 搜索插入位置

简单2 种解法

标签：数组、二分查找

题目、示例与约束

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

请必须使用时间复杂度为 O(log n) 的算法。

 

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

 

提示:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 为 无重复元素 的 升序 排列数组
• -104 <= target <= 104

方法一：二分查找 · Go 实现

思考

从左扫描到第一个不小于 $target$ 的位置，时间复杂度为 $O(n)$。在 $n\le {10}^4$ 的数据范围下可以接受，但数组已升序且无重复，线性遍历没有利用有序性。

插入位置恰好是第一个不小于 $target$ 的下标，即有序数组上的下界。为此维护半开区间 $[l,r)$：若 $nums[mid]\ge target$，则答案位于左半（含 $mid$）；否则位于 $mid$ 右侧。收缩至 $l=r$ 时， $l$ 即为插入点。

由于 $nums$ 数组已经有序，因此我们可以使用二分查找的方法找到目标值 $target$ 的插入位置。

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。其中 $n$ 为数组 $nums$ 的长度。

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

方法二：二分查找（内置函数） · Go 实现

思考

方法一已经达到 $O(\log n)$，仍需手写二分循环。各语言标准库均提供下界查找：Python 的 bisect_left、C++ 的 lower_bound、Java 的 Arrays.binarySearch（未找到时返回 $-i-1$）。语义与方法一相同，直接调用即可。

我们也可以直接使用内置函数进行二分查找。

时间复杂度 $O(\log n)$，其中 $n$ 为数组 $nums$ 的长度。空间复杂度 $O(1)$。

func searchInsert(nums []int, target int) int {
	return sort.SearchInts(nums, target)
}

力扣原题 · Doocs 题解来源

69. x 的平方根

简单1 种解法

标签：数学、二分查找、牛顿迭代法

题目、示例与约束

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

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

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

 

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

 

提示：

• 0 <= x <= 231 - 1

方法一：二分查找 · Go 实现

思考

题目要求不使用内置开方运算，求出不超过 $x$ 的最大整数平方根。若从 $0$ 线性枚举直至 $i^2>x$，则 $x$ 最大约为 $2^{31}-1$，扫描过慢，且 $i^2$ 容易溢出。

答案具有单调性：若 $mi{d}^2\le x$，则更大的候选仍可能合法，否则只能缩小上界。因此可以在 $[0,x]$ 上二分。比较时写成 $mid>x/mid$，避免乘法溢出；取上中位数并将区间收缩为「最大的可行值」，结束时左端点即为整数平方根。

我们定义二分查找的左边界 $l=0$，右边界 $r=x$，然后在 $[l,r]$ 范围内查找平方根。

在每一步查找中，我们找出中间值 $mid=(l+r+1)/2$，如果 $mid>x/mid$，说明平方根在 $[l,mid-1]$ 范围内，我们令 $r=mid-1$；否则说明平方根在 $[mid,r]$ 范围内，我们令 $l=mid$。

查找结束后，返回 $l$ 即可。

时间复杂度 $O(\log x)$，空间复杂度 $O(1)$。

func mySqrt(x int) int {
	return sort.Search(x+1, func(i int) bool { return i*i > x }) - 1
}

力扣原题 · Doocs 题解来源

74. 搜索二维矩阵

中等2 种解法

标签：数组、二分查找、矩阵

题目、示例与约束

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

你必须编写一个时间复杂度为 O(log(m * n)) 的解决方案。

 

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

 

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

方法一：二分查找 · Go 实现

思考

逐格扫描需要 $O(mn)$ 时间。 $m,n\le 100$ 可以接受，但题目要求 $O(\log (mn))$。

二维矩阵本身不便直接二分，但每一行递增，且上一行末尾小于下一行开头，因此按行拼接后是长度为 $mn$ 的有序序列。将逻辑下标 $mid$ 映射为 $matrix[\lfloor mid/n\rfloor ][midmodn]$，即可在 $[0,mn-1]$ 上做一次二分，不必真正展开数组。

我们将二维矩阵逻辑展开，然后二分查找即可。

时间复杂度 $O(\log (m\times n))$。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。空间复杂度 $O(1)$。

func searchMatrix(matrix [][]int, target int) bool {
	m, n := len(matrix), len(matrix[0])
	left, right := 0, m*n-1
	for left < right {
		mid := (left + right) >> 1
		x, y := mid/n, mid%n
		if matrix[x][y] >= target {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return matrix[left/n][left%n] == target
}

方法二：从左下角或右上角搜索 · Go 实现

思考

方法一已达到 $O(\log (mn))$，但需要把一维下标还原成行列坐标，并依赖「上一行末尾小于下一行开头」。

若只利用行、列各自单调，从左下角出发，一次比较即可排除一整行或一整列，实现不必做下标映射。代价是时间退化为 $O(m+n)$。

这里我们以左下角作为起始搜索点，往右上方向开始搜索，比较当前元素 $matrix[i][j]$ 与 $target$ 的大小关系：

• 若 $matrix[i][j]=target$，说明找到了目标值，直接返回 true。
• 若 $matrix[i][j]>target$，说明这一行从当前位置开始往右的所有元素均大于 target，应该让 i 指针往上移动，即 $i=i-1$。
• 若 $matrix[i][j]<target$，说明这一列从当前位置开始往上的所有元素均小于 target，应该让 j 指针往右移动，即 $j=j+1$。

若搜索结束依然找不到 $target$，返回 false。

时间复杂度 $O(m+n)$。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。空间复杂度 $O(1)$。

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

力扣原题 · Doocs 题解来源

81. 搜索旋转排序数组 II

中等1 种解法

标签：数组、二分查找

题目、示例与约束

已知存在一个按非降序排列的整数数组 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,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

 

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

 

提示：

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -104 <= target <= 104

 

进阶：

• 此题与 搜索旋转排序数组 相似，但本题中的 nums  可能包含 重复 元素。这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

 

方法一：二分查找 · Go 实现

思考

线性扫描每个元素并与 $\mathit{\text{target}}$ 比较， $n\le 5000$ 可以接受，但题目希望尽量减少操作，且旋转后的数组两段各自有序。

普通二分依赖全程有序；本题用 $\mathit{\text{nums}}[\mathit{\text{mid}}]$ 与 $\mathit{\text{nums}}[r]$ 比较，即可判断哪一侧有序，再看 $\mathit{\text{target}}$ 是否落在有序段内。与「搜索旋转排序数组」的差别在于允许重复：当 $\mathit{\text{nums}}[\mathit{\text{mid}}]=\mathit{\text{nums}}[r]$ 时无法判断哪边有序，只能将 $r$ 减一。最坏情况下整段相等，时间退化为 $O(n)$，这是重复元素带来的代价。

我们定义二分查找的左边界 $l=0$，右边界 $r=n-1$，其中 $n$ 为数组的长度。

每次在二分查找的过程中，我们会得到当前的中点 $\mathit{\text{mid}}=(l+r)/2$。

• 如果 $\mathit{\text{nums}}[\mathit{\text{mid}}]>\mathit{\text{nums}}[r]$，说明 $[l,\mathit{\text{mid}}]$ 是有序的，此时如果 $\mathit{\text{nums}}[l]\le \mathit{\text{target}}\le \mathit{\text{nums}}[\mathit{\text{mid}}]$，说明 $\mathit{\text{target}}$ 位于 $[l,\mathit{\text{mid}}]$，否则 $\mathit{\text{target}}$ 位于 $[\mathit{\text{mid}}+1,r]$。
• 如果 $\mathit{\text{nums}}[\mathit{\text{mid}}]<\mathit{\text{nums}}[r]$，说明 $[\mathit{\text{mid}}+1,r]$ 是有序的，此时如果 $\mathit{\text{nums}}[\mathit{\text{mid}}]<\mathit{\text{target}}\le \mathit{\text{nums}}[r]$，说明 $\mathit{\text{target}}$ 位于 $[\mathit{\text{mid}}+1,r]$，否则 $\mathit{\text{target}}$ 位于 $[l,\mathit{\text{mid}}]$。
• 如果 $\mathit{\text{nums}}[\mathit{\text{mid}}]=\mathit{\text{nums}}[r]$，说明元素 $\mathit{\text{nums}}[\mathit{\text{mid}}]$ 和 $\mathit{\text{nums}}[r]$ 相等，此时无法判断 $\mathit{\text{target}}$ 位于哪个区间，我们只能将 $r$ 减少 $1$。

二分查找结束后，如果 $\mathit{\text{nums}}[l]=\mathit{\text{target}}$，则说明数组中存在目标值 $\mathit{\text{target}}$，否则说明不存在。

时间复杂度 $O(n)$，其中 $n$ 为数组的长度。空间复杂度 $O(1)$。

我们定义二分查找的左边界 $l=0$，右边界 $r=n-1$，其中 $n$ 为数组的长度。

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

力扣原题 · Doocs 题解来源

153. 寻找旋转排序数组中的最小值

中等1 种解法

标签：数组、二分查找

题目、示例与约束

已知一个长度为 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) 的算法解决此问题。

 

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

 

提示：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums 中的所有整数 互不相同
• nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

方法一：二分查找 · Go 实现

思考

旋转后的有序数组没有重复，线性扫最小值是 $O(n)$， $n\le 5000$ 可以，但有序性允许对数。最小值把数组分成两段递增。与末元素比较：中点更大说明最小值在右半，否则在左半（含中点）。收缩到一点即答案。

我们可以使用二分查找来解决这个问题。

首先，我们定义两个指针 $l$ 和 $r$，分别指向数组的起始位置和结束位置。然后，我们进入一个循环，直到 $l$ 小于 $r$。

在每次循环中，我们计算中间位置 $mid$，并比较 $nums[mid]$ 和 $nums[n-1]$ 的值。如果 $nums[mid]$ 大于 $nums[n-1]$，说明最小值在 $mid$ 的右侧，因此我们将 $l$ 更新为 $mid+1$。否则，最小值在 $mid$ 的左侧或 $mid$ 本身，因此我们将 $r$ 更新为 $mid$。当循环结束时，指针 $l$ 将指向最小值的位置，我们返回 $nums[l]$ 即可。

时间复杂度 $O(\log n)$，其中 $n$ 是数组 $\mathit{\text{nums}}$ 的长度。空间复杂度 $O(1)$。

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

力扣原题 · Doocs 题解来源

154. 寻找旋转排序数组中的最小值 II

困难1 种解法

标签：数组、二分查找

题目、示例与约束

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

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
• 若旋转 7 次，则可以得到 [0,1,4,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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须尽可能减少整个过程的操作步骤。

 

示例 1：

输入：nums = [1,3,5]
输出：1

示例 2：

输入：nums = [2,2,2,0,1]
输出：0

 

提示：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

 

进阶：这道题与 寻找旋转排序数组中的最小值 类似，但 nums 可能包含重复元素。允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

方法一：二分查找 · Go 实现

思考

与上一题相比允许重复。 $\mathit{\text{nums}}[\mathit{\text{mid}}]=\mathit{\text{nums}}[r]$ 时无法判断最小值在哪一侧，只能把 $r$ 减一缩小范围。最坏全相等时退化为 $O(n)$，这是重复元素带来的代价。其余分支仍按旋转数组的二分收缩。

我们定义二分查找的左边界 $l=0$，右边界 $r=n-1$。每次计算中间位置 $mid=(l+r)\gg 1$，比较 $nums[mid]$ 和 $nums[r]$ 的大小关系：

• 如果 $nums[mid]>nums[r]$，说明最小值在 $mid$ 的右侧，因此将 $l$ 更新为 $mid+1$。
• 如果 $nums[mid]=nums[r]$，无法确定最小值的位置，但可以将 $r$ 向左移动一位，即 $r=r-1$，以缩小搜索范围。
• 如果 $nums[mid]<nums[r]$，说明最小值在 $mid$ 的左侧或 $mid$ 本身，因此将 $r$ 更新为 $mid$。

当 $l$ 与 $r$ 相遇时，指针 $l$ 就指向了最小值的位置，返回 $nums[l]$ 即可。

时间复杂度 $O(n)$，最坏情况下数组中所有元素都相同，需要遍历整个数组。空间复杂度 $O(1)$。

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

力扣原题 · Doocs 题解来源

162. 寻找峰值

中等1 种解法

标签：数组、二分查找

题目、示例与约束

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

 

示例 1：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

 

提示：

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• 对于所有有效的 i 都有 nums[i] != nums[i + 1]

方法一：二分查找 · Go 实现

思考

相邻元素不同，两端外侧视为负无穷，峰值一定存在。线性扫描 $n\le 1000$ 可以，题目希望 $O(\log n)$。比较中点与右侧：右侧更小则左半（含中点）存在峰值，否则右半存在。不断缩小，相遇即峰值下标。

我们定义二分查找的左边界 $left=0$，右边界 $right=n-1$，其中 $n$ 是数组的长度。在每一步二分查找中，我们找到当前区间的中间元素 $mid$，然后比较 $mid$ 与其右边元素 $mid+1$ 的值：

• 如果 $mid$ 的值大于 $mid+1$ 的值，则左侧存在峰值元素，我们将右边界 $right$ 更新为 $mid$；
• 否则，右侧存在峰值元素，我们将左边界 $left$ 更新为 $mid+1$。
• 最后，当左边界 $left$ 与右边界 $right$ 相等时，我们就找到了数组的峰值元素。

时间复杂度 $O(\log n)$，其中 $n$ 是数组 $nums$ 的长度。每一步二分查找可以将搜索区间减少一半，因此时间复杂度为 $O(\log n)$。空间复杂度 $O(1)$。

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

力扣原题 · Doocs 题解来源

167. 两数之和 II - 输入有序数组

中等2 种解法

标签：数组、双指针、二分查找

题目、示例与约束

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列。

请你从数组中找出满足相加之和等于目标数 target 的 两个 数。令这两个数分别是 numbers[index1] 和 numbers[index2] ，其中 1 <= index1 < index2 <= numbers.length 。

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

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

你所设计的解决方案必须只使用常数级的额外空间。

 

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

 

提示：

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers 按 非递减顺序 排列
• -1000 <= target <= 1000
• 仅存在一个有效答案

方法一：二分查找 · Go 实现

思考

有序数组上的两数之和，下标从 $1$ 计，恰好一对答案。哈希表是 $O(n)$ 空间。对每个 $numbers[i]$ 在右侧二分 $target-numbers[i]$， $n\le 3\times {10}^4$，时间 $O(n\log n)$，空间 $O(1)$。

我们注意到数组按照非递减顺序排列，因此对于每个 $numbers[i]$，可以通过二分查找的方式找到 $target-numbers[i]$ 的位置，如果存在，那么返回 $[i+1,j+1]$ 即可。

时间复杂度 $O(n\times \log n)$，其中 $n$ 为数组 $numbers$ 的长度。空间复杂度 $O(1)$。

func twoSum(numbers []int, target int) []int {
	for i, n := 0, len(numbers); ; i++ {
		x := target - numbers[i]
		j := sort.SearchInts(numbers[i+1:], x) + i + 1
		if j < n && numbers[j] == x {
			return []int{i + 1, j + 1}
		}
	}
}

方法二：双指针 · Go 实现

思考

方法一每个左端点都要二分。两端指针相向：和偏小则左指针右移，偏大则右指针左移。有序性保证不会漏掉唯一解，时间降为 $O(n)$。

我们定义两个指针 $i$ 和 $j$，分别指向数组的第一个元素和最后一个元素。每次计算 $numbers[i]+numbers[j]$，如果和等于目标值，那么返回 $[i+1,j+1]$ 即可。如果和小于目标值，那么将 $i$ 右移一位，如果和大于目标值，那么将 $j$ 左移一位。

时间复杂度 $O(n)$，其中 $n$ 为数组 $numbers$ 的长度。空间复杂度 $O(1)$。

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

力扣原题 · Doocs 题解来源

209. 长度最小的子数组

中等2 种解法

标签：数组、二分查找、前缀和、滑动窗口

题目、示例与约束

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

 

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

 

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104

 

进阶：

• 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

方法一：前缀和 + 二分查找 · Go 实现

思考

枚举全部子数组求和需 $O(n^2)$。元素均为正整数，前缀和单调递增，固定左端后最短右端可用二分定位。

为此先求前缀和 $s$，对每个 $s[i]$ 二分最小的 $j$ 使 $s[j]\ge s[i]+\mathit{\text{target}}$，用 $j-i$ 更新最短长度。

我们先预处理出数组 $nums$ 的前缀和数组 $s$，其中 $s[i]$ 表示数组 $nums$ 前 $i$ 项元素之和。由于数组 $nums$ 中的元素都是正整数，因此数组 $s$ 也是单调递增的。另外，我们初始化答案 $ans=n+1$，其中 $n$ 为数组 $nums$ 的长度。

接下来，我们遍历前缀和数组 $s$，对于其中的每个元素 $s[i]$，我们可以通过二分查找的方法找到满足 $s[j]\ge s[i]+target$ 的最小下标 $j$，如果 $j\le n$，则说明存在满足条件的子数组，我们可以更新答案，即 $ans=min(ans,j-i)$。

最后，如果 $ans\le n$，则说明存在满足条件的子数组，返回 $ans$，否则返回 $0$。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $nums$ 的长度。

func minSubArrayLen(target int, nums []int) int {
	n := len(nums)
	s := make([]int, n+1)
	for i, x := range nums {
		s[i+1] = s[i] + x
	}
	ans := n + 1
	for i, x := range s {
		j := sort.SearchInts(s, x+target)
		if j <= n {
			ans = min(ans, j-i)
		}
	}
	if ans == n+1 {
		return 0
	}
	return ans
}

方法二：双指针 · Go 实现

思考

前缀和加二分仍占用 $O(n)$ 空间，并多一个对数因子。正数保证窗口和随右端增大、随左端右移而减小。

为此用双指针维护当前和：右端纳入新元素，当和不少于 $\mathit{\text{target}}$ 时收缩左端并更新最短长度。

我们注意到，数组 $\mathit{\text{nums}}$ 中的元素均为正整数，我们可以考虑使用双指针来维护一个滑动窗口。

具体地，我们定义两个指针 $\mathit{\text{l}}$ 和 $\mathit{\text{r}}$ 分别表示滑动窗口的左边界和右边界，用一个变量 $\mathit{\text{s}}$ 代表滑动窗口中的元素和。

在每一步操作中，我们移动右指针 $\mathit{\text{r}}$，使得滑动窗口中加入一个元素，如果此时 $\mathit{\text{s}}\ge \mathit{\text{target}}$，我们就更新最小长度 $\mathit{\text{ans}}=min(\mathit{\text{ans}},\mathit{\text{r}}-\mathit{\text{l}}+1$，并将左指针 $\mathit{\text{l}}$ 循环向右移动，直至有 $\mathit{\text{s}}<\mathit{\text{target}}$。

最后，如果最小长度 $\mathit{\text{ans}}$ 仍为初始值，我们就返回 $0$，否则返回 $\mathit{\text{ans}}$。

时间复杂度 $O(n)$，其中 $n$ 为数组 $\mathit{\text{nums}}$ 的长度。空间复杂度 $O(1)$。

func minSubArrayLen(target int, nums []int) int {
	l, n := 0, len(nums)
	s, ans := 0, n+1
	for r, x := range nums {
		s += x
		for s >= target {
			ans = min(ans, r-l+1)
			s -= nums[l]
			l++
		}
	}
	if ans > n {
		return 0
	}
	return ans
}

力扣原题 · Doocs 题解来源

240. 搜索二维矩阵 II

中等2 种解法

标签：数组、二分查找、分治、矩阵

题目、示例与约束

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

 

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

 

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -109 <= matrix[i][j] <= 109
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -109 <= target <= 109

方法一：二分查找 · Go 实现

思考

每行、每列均递增，可对每一行二分查找 $target$。行数为 $m$、列为 $n$ 时时间为 $O(m\log n)$，无需额外空间。

由于每一行的所有元素升序排列，因此，对于每一行，我们可以使用二分查找找到第一个大于等于 $\mathit{\text{target}}$ 的元素，然后判断该元素是否等于 $\mathit{\text{target}}$。如果等于 $\mathit{\text{target}}$，说明找到了目标值，直接返回 $\text{true}$。如果不等于 $\mathit{\text{target}}$，说明这一行的所有元素都小于 $\mathit{\text{target}}$，应该继续搜索下一行。

如果所有行都搜索完了，都没有找到目标值，说明目标值不存在，返回 $\text{false}$。

时间复杂度 $O(m\times \log n)$，其中 $m$ 和 $n$ 分别为矩阵的行数和列数。空间复杂度 $O(1)$。

func searchMatrix(matrix [][]int, target int) bool {
	for _, row := range matrix {
		j := sort.SearchInts(row, target)
		if j < len(matrix[0]) && row[j] == target {
			return true
		}
	}
	return false
}

方法二：从左下角或右上角搜索 · Go 实现

思考

逐行二分未同时利用列递增。从左下角出发：当前值过大则上移（排除本列上方），过小则右移（排除本行右侧）。

每步丢掉一行或一列，时间为 $O(m+n)$。

这里我们以左下角或右上角作为起始搜索点，往右上或左下方向开始搜索。比较当前元素 $\mathit{\text{matrix}}[i][j]$ 与 $\mathit{\text{target}}$ 的大小关系：

• 若 $\mathit{\text{matrix}}[i][j]=\mathit{\text{target}}$，说明找到了目标值，直接返回 $\text{true}$。
• 若 $\mathit{\text{matrix}}[i][j]>\mathit{\text{target}}$，说明这一列从当前位置开始往上的所有元素均大于 $\mathit{\text{target}}$，应该让 $i$ 指针往上移动，即 $i\leftarrow i-1$。
• 若 $\mathit{\text{matrix}}[i][j]<\mathit{\text{target}}$，说明这一行从当前位置开始往右的所有元素均小于 $\mathit{\text{target}}$，应该让 $j$ 指针往右移动，即 $j\leftarrow j+1$。

若搜索结束依然找不到 $\mathit{\text{target}}$，返回 $\text{false}$。

时间复杂度 $O(m+n)$，其中 $m$ 和 $n$ 分别为矩阵的行数和列数。空间复杂度 $O(1)$。

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

力扣原题 · Doocs 题解来源

259. 较小的三数之和 🔒

中等1 种解法

标签：数组、双指针、二分查找、排序

题目、示例与约束

给定一个长度为 n 的整数数组和一个目标值 target ，寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组  i, j, k 个数（0 <= i < j < k < n）。

 

示例 1：

输入: nums = [-2,0,1,3], target = 2
输出: 2 
解释: 因为一共有两个三元组满足累加和小于 2:
     [-2,0,1]
     [-2,0,3]

示例 2：

输入: nums = [], target = 0
输出: 0 

示例 3：

输入: nums = [0], target = 0
输出: 0 

 

提示:

• n == nums.length
• 0 <= n <= 3500
• -100 <= nums[i] <= 100
• -100 <= target <= 100
• 输入保证答案小于或等于 10⁹。

方法一：排序 + 双指针 + 枚举 · Go 实现

思考

三元组顺序无关，可先排序。固定最小下标 $i$ 后，在右侧用双指针统计和小于 $\mathit{\text{target}}$ 的对数。

若 $nums[i]+nums[j]+nums[k]<\mathit{\text{target}}$，则 $j$ 与 $(j,k]$ 中每个 $k^{\prime }$ 都合法，一次加上 $k-j$ 并右移 $j$；否则左移 $k$。

由于元素的顺序不影响结果，我们可以先对数组进行排序，然后使用双指针的方法来解决这个问题。

我们先将数组排序，然后枚举第一个元素 $\mathit{\text{nums}}[i]$，并在 $\mathit{\text{nums}}[i+1:n-1]$ 的区间内使用双指针分别指向 $\mathit{\text{nums}}[j]$ 和 $\mathit{\text{nums}}[k]$，其中 $j$ 是 $\mathit{\text{nums}}[i]$ 的下一个元素，而 $k$ 是数组的最后一个元素。

• 如果 $\mathit{\text{nums}}[i]+\mathit{\text{nums}}[j]+\mathit{\text{nums}}[k]<\mathit{\text{target}}$，那么对于任意 $j<k^{\prime }\le k$ 的元素，都有 $\mathit{\text{nums}}[i]+\mathit{\text{nums}}[j]+\mathit{\text{nums}}[k^{\prime }]<\mathit{\text{target}}$，一共有 $k-j$ 个这样的 $k^{\prime }$，我们将 $k-j$ 累加到答案中。接下来，将 $j$ 右移一个位置，继续寻找下一个满足条件的 $k$，直到 $j\ge k$ 为止。
• 如果 $\mathit{\text{nums}}[i]+\mathit{\text{nums}}[j]+\mathit{\text{nums}}[k]\ge \mathit{\text{target}}$，那么对于任意 $j\le j^{\prime }<k$ 的元素，都不可能使得 $\mathit{\text{nums}}[i]+\mathit{\text{nums}}[j^{\prime }]+\mathit{\text{nums}}[k]<\mathit{\text{target}}$，因此我们将 $k$ 左移一个位置，继续寻找下一个满足条件的 $k$，直到 $j\ge k$ 为止。

枚举完所有的 $i$ 后，我们就得到了满足条件的三元组的个数。

时间复杂度 $O(n^2)$，空间复杂度 $O(\log n)$。其中 $n$ 是数组 $\mathit{\text{nums}}$ 的长度。

func threeSumSmaller(nums []int, target int) (ans int) {
	sort.Ints(nums)
	n := len(nums)
	for i := 0; i < n-2; i++ {
		j, k := i+1, n-1
		for j < k {
			x := nums[i] + nums[j] + nums[k]
			if x < target {
				ans += k - j
				j++
			} else {
				k--
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

268. 丢失的数字

简单2 种解法

标签：位运算、数组、哈希表、数学、二分查找、排序

题目、示例与约束

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

 

示例 1：

输入：nums = [3,0,1]

输出：2

解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：

输入：nums = [0,1]

输出：2

解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 3：

输入：nums = [9,6,4,2,3,5,7,0,1]

输出：8

解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。

提示：

• n == nums.length
• 1 <= n <= 104
• 0 <= nums[i] <= n
• nums 中的所有数字都 独一无二

 

进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

方法一：位运算 · Go 实现

思考

$[0,n]$ 中缺一个数。把下标 $1..n$ 与数组元素全部异或，成对抵消后剩下缺失值。

异或运算的性质：

• 任何数和 $0$ 做异或运算，结果仍然是原来的数，即 $x\oplus 0=x$；
• 任何数和其自身做异或运算，结果是 $0$，即 $x\oplus x=0$；

因此，我们可以遍历数组，将数字 $[0,..n]$ 与数组中的元素进行异或运算，最后的结果就是缺失的数字。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组长度。

func missingNumber(nums []int) (ans int) {
	n := len(nums)
	ans = n
	for i, v := range nums {
		ans ^= (i ^ v)
	}
	return
}

方法二：数学 · Go 实现

思考

异或不依赖加法。也可用高斯求和： $n(n+1)/2$ 减去数组之和即缺失数。

我们也可以用数学求解。求出 $[0,..n]$ 的和，减去数组中所有数的和，就得到了缺失的数字。

时间复杂度 $O(n)$，其中 $n$ 为数组长度。空间复杂度 $O(1)$。

func missingNumber(nums []int) (ans int) {
	n := len(nums)
	ans = n
	for i, v := range nums {
		ans += i - v
	}
	return
}

力扣原题 · Doocs 题解来源

275. H 指数 II

中等1 种解法

标签：数组、二分查找

题目、示例与约束

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 非降序排列 。计算并返回该研究者的 h 指数。

h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）至少 有 h 篇论文分别被引用了至少 h 次。

请你设计并实现对数时间复杂度的算法解决此问题。

 

示例 1：

输入：citations = [0,1,3,5,6]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
     由于研究者有3篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3 。

示例 2：

输入：citations = [1,2,100]
输出：2

 

提示：

• n == citations.length
• 1 <= n <= 105
• 0 <= citations[i] <= 1000
• citations 按 升序排列

方法一：二分查找 · Go 实现

思考

数组已升序，上一题的排序可以省去。 $citations[n-h]\ge h$ 当且仅当 $h$ 可行，对 $h$ 二分即可在对数时间内得到最大 $h$。

我们注意到，如果有至少 $x$ 篇论文的引用次数大于等于 $x$，那么对于任意 $y<x$，其引用次数也一定大于等于 $y$。这存在着单调性。

因此，我们二分枚举 $h$，获取满足条件的最大 $h$。由于要满足 $h$ 篇论文至少被引用 $h$ 次，因此 $citations[n-mid]\ge mid$。

时间复杂度 $O(\log n)$，其中 $n$ 是数组 $citations$ 的长度。空间复杂度 $O(1)$。

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

力扣原题 · Doocs 题解来源

278. 第一个错误的版本

简单1 种解法

标签：二分查找、交互

题目、示例与约束

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

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

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

 

示例 1：

输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false 
调用 isBadVersion(5) -> true 
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

示例 2：

输入：n = 1, bad = 1
输出：1

 

提示：

• 1 <= bad <= n <= 231 - 1

方法一：二分查找 · Go 实现

思考

版本一旦变坏则之后全坏，具有单调性。对 $isBadVersion(\mathit{\text{mid}})$ 为真则答案在左侧含 $\mathit{\text{mid}}$，否则在右侧。

二分收缩到 $l=r$ 即为第一个坏版本。

我们定义二分查找的左边界 $l=1$，右边界 $r=n$。

当 $l<r$ 时，我们计算中间位置 $\mathit{\text{mid}}=\lfloor \frac{l+r}{2}\rfloor$，然后调用 isBadVersion(mid) 接口，如果返回 $\mathit{\text{true}}$，则说明第一个错误的版本在 $[l,\mathit{\text{mid}}]$ 之间，我们令 $r=\mathit{\text{mid}}$；否则第一个错误的版本在 $[\mathit{\text{mid}}+1,r]$ 之间，我们令 $l=\mathit{\text{mid}}+1$。

最终返回 $l$ 即可。

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。

/**
 * Forward declaration of isBadVersion API.
 * @param   version   your guess about first bad version
 * @return 	 	      true if current version is bad
 *			          false if current version is good
 * func isBadVersion(version int) bool;
 */

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
}

力扣原题 · Doocs 题解来源

287. 寻找重复数

中等1 种解法

标签：位运算、数组、双指针、二分查找、Floyd 判圈算法、抽屉原理

题目、示例与约束

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

 

示例 1：

输入：nums = [1,3,4,2,2]
输出：2

示例 2：

输入：nums = [3,1,3,4,2]
输出：3

示例 3 :

输入：nums = [3,3,3,3,3]
输出：3

 

 

提示：

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

 

进阶：

• 如何证明 nums 中至少存在一个重复的数字?
• 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

方法一：二分查找 · Go 实现

思考

不能改数组且只用常数空间，排序或哈希都不符合。抽屉原理： $[1,x]$ 中若出现次数大于 $x$，则重复值落在该段。

对值域二分，统计 $\le mid$ 的个数，大于 $mid$ 则答案在左侧，否则在右侧。

我们可以发现，如果 $[1,..x]$ 中的数字个数大于 $x$，那么重复的数字一定在 $[1,..x]$ 中，否则重复的数字一定在 $[x+1,..n]$ 中。

因此，我们可以二分枚举 $x$，每次判断 $[1,..x]$ 中的数字个数是否大于 $x$，从而确定重复的数字在哪个区间中，进而缩小区间范围，直到找到重复的数字。

时间复杂度 $O(n\times \log n)$，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(1)$。

func findDuplicate(nums []int) int {
	return sort.Search(len(nums), func(x int) bool {
		cnt := 0
		for _, v := range nums {
			if v <= x {
				cnt++
			}
		}
		return cnt > x
	})
}

力扣原题 · Doocs 题解来源

349. 两个数组的交集

简单1 种解法

标签：数组、哈希表、双指针、二分查找、排序

题目、示例与约束

给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

 

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

 

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

方法一：哈希表或数组 · Go 实现

思考

两数组的去重交集。双重循环配对数为 $O(nm)$。值域或哈希可 $O(1)$ 查询。

把一边放入集合，扫另一边并在命中后删除以免重复。代码直接求两集合之交。

我们先用哈希表或者一个长度为 $1001$ 的数组 $s$ 记录数组 $nums1$ 中出现的元素，然后遍历数组 $nums2$ 中每个元素，如果元素 $x$ 在 $s$ 中，那么将 $x$ 加入答案，并且从 $s$ 中移除 $x$。

遍历结束后，返回答案数组即可。

时间复杂度 $O(n+m)$，空间复杂度 $O(n)$。其中 $n$ 和 $m$ 分别是数组 $nums1$ 和 $nums2$ 的长度。

func intersection(nums1 []int, nums2 []int) (ans []int) {
	s := [1001]bool{}
	for _, x := range nums1 {
		s[x] = true
	}
	for _, x := range nums2 {
		if s[x] {
			ans = append(ans, x)
			s[x] = false
		}
	}
	return
}

力扣原题 · Doocs 题解来源

350. 两个数组的交集 II

简单1 种解法

标签：数组、哈希表、双指针、二分查找、排序

题目、示例与约束

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

 

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

 

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

 

进阶：

• 如果给定的数组已经排好序呢？你将如何优化你的算法？
• 如果 nums1 的大小比 nums2 小，哪种方法更优？
• 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

方法一：哈希表 · Go 实现

思考

交集须保留出现次数，取两边的较小频次。相对 349，不能去重到一次。

统计 $nums1$ 的频次，扫 $nums2$：尚有余额则写入答案并减一。输出长度等于各值 $min$ 次数之和。

我们可以用一个哈希表 $\mathit{\text{cnt}}$ 统计数组 $\mathit{\text{nums1}}$ 中每个元素出现的次数，然后遍历数组 $\mathit{\text{nums2}}$，如果元素 $x$ 在 $\mathit{\text{cnt}}$ 中，并且 $x$ 的出现次数大于 $0$，那么将 $x$ 加入答案，然后将 $x$ 的出现次数减一。

遍历结束后，返回答案数组即可。

时间复杂度 $O(m+n)$，空间复杂度 $O(m)$。其中 $m$ 和 $n$ 分别是数组 $\mathit{\text{nums1}}$ 和 $\mathit{\text{nums2}}$ 的长度。

func intersect(nums1 []int, nums2 []int) (ans []int) {
	cnt := map[int]int{}
	for _, x := range nums1 {
		cnt[x]++
	}
	for _, x := range nums2 {
		if cnt[x] > 0 {
			ans = append(ans, x)
			cnt[x]--
		}
	}
	return
}

力扣原题 · Doocs 题解来源

363. 矩形区域不超过 K 的最大数值和

困难1 种解法

标签：数组、二分查找、矩阵、有序集合、前缀和

题目、示例与约束

给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。

题目数据保证总会存在一个数值和不超过 k 的矩形区域。

 

示例 1：

输入：matrix = [[1,0,1],[0,-2,3]], k = 2
输出：2
解释：蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。

示例 2：

输入：matrix = [[2,2,-1]], k = 3
输出：3

 

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -100 <= matrix[i][j] <= 100
• -105 <= k <= 105

 

进阶：如果行数远大于列数，该如何设计解决方案？

方法一：枚举边界 + 有序集合 · Go 实现

思考

子矩形和不超过 $k$ 的最大值。枚举四边界为 $O(m^2{n}^2)$。固定上下边界后，每列压缩成一维，问题化为和 $\le k$ 的最大子段和。

有序集合维护前缀：对当前和 $s$ 查找最小的 $t\ge s-k$，则 $s-t$ 不超过 $k$ 且尽量大。上下边界枚举 $O(m^2)$，一维 $O(n\log n)$。

我们可以枚举矩形的上下边界 $i$ 和 $j$，然后计算出该边界内每列的元素和，记录在数组 $nums$ 中，问题转化为如何在数组 $nums$ 中寻找不超过 $k$ 的最大子数组和。

我们可以使用有序集合来快速寻找小于等于 $x$ 的最大值，从而得到最大子数组和不超过 $k$ 的子数组。

时间复杂度 $O(m^2\times n\times \log n)$，空间复杂度 $O(n)$。

func maxSumSubmatrix(matrix [][]int, k int) int {
	m, n := len(matrix), len(matrix[0])
	const inf = 1 << 30
	ans := -inf
	for i := 0; i < m; i++ {
		nums := make([]int, n)
		for j := i; j < m; j++ {
			for h := 0; h < n; h++ {
				nums[h] += matrix[j][h]
			}
			s := 0
			rbt := redblacktree.NewWithIntComparator()
			rbt.Put(0, nil)
			for _, x := range nums {
				s += x
				if y, ok := rbt.Ceiling(s - k); ok {
					ans = max(ans, s-y.Key.(int))
				}
				rbt.Put(s, nil)
			}
		}

	}
	return ans
}

力扣原题 · Doocs 题解来源

367. 有效的完全平方数

简单2 种解法

标签：数学、二分查找

题目、示例与约束

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

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如  sqrt 。

 

示例 1：

输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

示例 2：

输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

 

提示：

• 1 <= num <= 231 - 1

方法一：二分查找 · Go 实现

思考

判断 $num$ 是否完全平方。从 $1$ 扫到 $\sqrt{num}$ 为 $O(\sqrt{n})$。在值域上对 $x^2$ 二分即可。

在 $[1,num]$ 中找最小的 $x$ 使 $x^2\ge num$，再检查是否相等。代码用 bisect_left 配 $x\mapsto x^2$。

我们可以使用二分查找来解决这个问题。定义二分查找的左边界 $l=1$，右边界 $r=num$，然后在 $[l,r]$ 的范围内查找满足 $x^2\ge num$ 的最小整数 $x$。最后，如果 $x^2=num$，则说明 $num$ 是一个完全平方数。

时间复杂度 $O(\log n)$，其中 $n$ 是给定的数字。空间复杂度 $O(1)$。

func isPerfectSquare(num int) bool {
	l := sort.Search(num, func(i int) bool { return i*i >= num })
	return l*l == num
}

方法二：数学 · Go 实现

思考

二分依赖有序平方。奇数和 $1+3+\cdots +(2n-1)=n^2$，故反复减递增奇数，减到 $0$ 则为平方。实现更短，时间为 $O(\sqrt{n})$。

由于 $1+3+5+\cdots +(2n-1)=n^2$，我们可以将 $num$ 逐渐减去 $1,3,5,\cdots$，如果最后 $num=0$，则说明 $num$ 是一个完全平方数。

时间复杂度 $O(\sqrt{n})$，空间复杂度 $O(1)$。

func isPerfectSquare(num int) bool {
	for i := 1; num > 0; i += 2 {
		num -= i
	}
	return num == 0
}

力扣原题 · Doocs 题解来源

374. 猜数字大小

简单1 种解法

标签：二分查找、交互

题目、示例与约束

我们正在玩猜数字游戏。猜数字游戏的规则如下：

我会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。（我选的数字在整个游戏中保持不变）。

如果你猜错了，我会告诉你，我选出的数字比你猜测的数字大了还是小了。

你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有三种可能的情况：

• -1：你猜的数字比我选出的数字大 （即 num > pick）。
• 1：你猜的数字比我选出的数字小 （即 num < pick）。
• 0：你猜的数字与我选出的数字相等。（即 num == pick）。

返回我选出的数字。

 

示例 1：

输入：n = 10, pick = 6
输出：6

示例 2：

输入：n = 1, pick = 1
输出：1

示例 3：

输入：n = 2, pick = 1
输出：1

 

提示：

• 1 <= n <= 231 - 1
• 1 <= pick <= n

方法一：二分查找 · Go 实现

思考

在 $[1,n]$ 中猜数，guess 告诉偏大或偏小。线性试探最坏 $n$ 次。有序区间上标准二分。

找第一个使 guess(x)\le 0 的 $x$，即所猜之数。代码把比较键写成 $-guess(x)$，用 bisect 一次完成。

我们在区间 $[1,..n]$ 进行二分查找，找到第一个满足 guess(x) <= 0 的数，即为答案。

时间复杂度 $O(\log n)$。其中 $n$ 为题目给定的上限。空间复杂度 $O(1)$。

/**
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is higher than the picked number
 *			      1 if num is lower than the picked number
 *               otherwise return 0
 * func guess(num int) int;
 */

func guessNumber(n int) int {
	return sort.Search(n, func(i int) bool {
		i++
		return guess(i) <= 0
	}) + 1
}

力扣原题 · Doocs 题解来源

378. 有序矩阵中第 K 小的元素

中等1 种解法

标签：数组、二分查找、矩阵、排序、堆（优先队列）

题目、示例与约束

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

你必须找到一个内存复杂度优于 O(n2) 的解决方案。

 

示例 1：

输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13

示例 2：

输入：matrix = [[-5]], k = 1
输出：-5

 

提示：

• n == matrix.length
• n == matrix[i].length
• 1 <= n <= 300
• -109 <= matrix[i][j] <= 109
• 题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列
• 1 <= k <= n2

 

进阶：

• 你能否用一个恒定的内存(即 O(1) 内存复杂度)来解决这个问题?
• 你能在 O(n) 的时间复杂度下解决这个问题吗?这个方法对于面试来说可能太超前了，但是你会发现阅读这篇文章（ this paper ）很有趣。

方法一 · Go 实现

思考

每行每列递增，求第 $k$ 小。展开排序为 $O(n^2\log n)$。第 $k$ 小必在 $[matrix[0][0],matrix[n-1][n-1]]$，可对值二分。

check(mid) 从左下（或右上）统计 $\le mid$ 的个数，利用单调性 $O(n)$。个数 $\ge k$ 则收缩右界。答案为最小可行 $mid$。

func kthSmallest(matrix [][]int, k int) int {
	n := len(matrix)
	left, right := matrix[0][0], matrix[n-1][n-1]
	for left < right {
		mid := (left + right) >> 1
		if check(matrix, mid, k, n) {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

func check(matrix [][]int, mid, k, n int) bool {
	count := 0
	i, j := n-1, 0
	for i >= 0 && j < n {
		if matrix[i][j] <= mid {
			count += (i + 1)
			j++
		} else {
			i--
		}
	}
	return count >= k
}

力扣原题 · Doocs 题解来源

400. 第 N 位数字

中等1 种解法

标签：数学、二分查找

题目、示例与约束

给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。

 

示例 1：

输入：n = 3
输出：3

示例 2：

输入：n = 11
输出：0
解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。

 

提示：

• 1 <= n <= 231 - 1

方法一：数学 · Go 实现

思考

若将整数逐个拼接成字符串再取第 $n$ 位， $n$ 可达 $2^{31}-1$，整段序列无法物化。

同一位数的整数所贡献的位数可以闭式求出： $k$ 位数共 $9\times {10}^{k-1}$ 个，合计 $k\times 9\times {10}^{k-1}$ 位。因此先按 $k$ 从 $1$ 递增，用减法判断 $n$ 落在哪一段，再由剩余偏移算出具体整数及其内部下标。

必须先扣完整段再定位，才能把「全局第 $n$ 位」化成「某个数的第 $\mathit{\text{idx}}$ 位」。

位数为 $k$ 的最小整数和最大整数分别为 ${10}^{k-1}$ 和 ${10}^k-1$，因此 $k$ 位数的总位数为 $k\times 9\times {10}^{k-1}$。

我们用 $k$ 表示当前数字的位数，用 $cnt$ 表示当前位数的数字的总数，初始时 $k=1$, $cnt=9$。

每次将 $n$ 减去 $cnt\times k$，当 $n$ 小于等于 $cnt\times k$ 时，说明 $n$ 对应的数字在当前位数的数字范围内，此时可以计算出对应的数字。

具体做法是，首先计算出 $n$ 对应的是当前位数的哪一个数字，然后计算出是该数字的第几位，从而得到该位上的数字。

时间复杂度 $O({\log }_{10}n)$。

func findNthDigit(n int) int {
	k, cnt := 1, 9
	for k*cnt < n {
		n -= k * cnt
		k++
		cnt *= 10
	}
	num := int(math.Pow10(k-1)) + (n-1)/k
	idx := (n - 1) % k
	return int(strconv.Itoa(num)[idx] - '0')
}

力扣原题 · Doocs 题解来源

436. 寻找右区间

中等1 种解法

标签：数组、二分查找、排序

题目、示例与约束

给你一个区间数组 intervals ，其中 intervals[i] = [starti, endi] ，且每个 starti 都 不同 。

区间 i 的 右侧区间 是满足 startj >= endi，且 startj 最小 的区间 j。注意 i 可能等于 j 。

返回一个由每个区间 i 对应的 右侧区间 下标组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。

 

示例 1：

输入：intervals = [[1,2]]
输出：[-1]
解释：集合中只有一个区间，所以输出-1。

示例 2：

输入：intervals = [[3,4],[2,3],[1,2]]
输出：[-1,0,1]
解释：对于 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间[3,4]具有最小的“右”起点;
对于 [1,2] ，区间[2,3]具有最小的“右”起点。

示例 3：

输入：intervals = [[1,4],[2,3],[3,4]]
输出：[-1,2,-1]
解释：对于区间 [1,4] 和 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间 [3,4] 有最小的“右”起点。

 

提示：

• 1 <= intervals.length <= 2 * 104
• intervals[i].length == 2
• -106 <= starti <= endi <= 106
• 每个间隔的起点都 不相同

方法一：排序 + 二分查找 · Go 实现

思考

每个区间要找起点不小于其终点、且起点最小的区间。对每个终点线性扫描是 $O(n^2)$。

把 $(\mathit{\text{start}},\mathit{\text{index}})$ 按起点排序，对每个终点二分第一个 $\mathit{\text{start}}\ge \mathit{\text{end}}$。

排序后起点单调，二分给出「最靠左的合法起点」，下标一并存入以免排序打乱对应关系。

我们可以将区间的起点和下标存入数组 arr 中，并按照起点进行排序。然后遍历区间数组，对于每个区间 [_, ed]，我们可以使用二分查找找到第一个起点大于等于 ed 的区间，即为其右侧区间，如果找到了，我们就将其下标存入答案数组中，否则存入 -1。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为区间的长度。

func findRightInterval(intervals [][]int) (ans []int) {
	arr := make([][2]int, len(intervals))
	for i, v := range intervals {
		arr[i] = [2]int{v[0], i}
	}
	sort.Slice(arr, func(i, j int) bool { return arr[i][0] < arr[j][0] })
	for _, e := range intervals {
		j := sort.Search(len(arr), func(i int) bool { return arr[i][0] >= e[1] })
		if j < len(arr) {
			ans = append(ans, arr[j][1])
		} else {
			ans = append(ans, -1)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

441. 排列硬币

简单2 种解法

标签：数学、二分查找

题目、示例与约束

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

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

 

示例 1：

输入：n = 5
输出：2
解释：因为第三行不完整，所以返回 2 。

示例 2：

输入：n = 8
输出：3
解释：因为第四行不完整，所以返回 3 。

 

提示：

• 1 <= n <= 231 - 1

方法一：数学推导 · Go 实现

思考

第 $x$ 行用 $x$ 枚硬币，完整行数满足 $x(x+1)/2\le n$。枚举 $x$ 是线性的， $n$ 可达 $2^{31}-1$。

解不等式得到 $x\le \sqrt{2}\sqrt{n+1/8}-1/2$，直接取整。把 $2n$ 拆成 $\sqrt{2}\sqrt{n+1/8}$，减轻中间溢出。

闭式一次求值，代价为常数次浮点运算。

(1 + x) * x / 2 <= n，求解 x。

(x + 1/2)² <= 2n + 1/4，即 x <= sqrt(2n + 1/4) - 1/2。

由于 2n 可能溢出，故转换为 x <= sqrt(2) * sqrt(n + 1/8) - 1/2。

func arrangeCoins(n int) int {
	return int(math.Sqrt(2)*math.Sqrt(float64(n)+0.125) - 0.5)
}

方法二：二分查找 · Go 实现

思考

方法一依赖浮点开方，极大 $n$ 时精度可能偏差。对行数二分：判断 $mid(mid+1)/2\le n$，上取整更新左界，只用整数运算。

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

力扣原题 · Doocs 题解来源

456. 132 模式

中等2 种解法

标签：栈、数组、二分查找、有序集合、单调栈

题目、示例与约束

给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。

如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。

 

示例 1：

输入：nums = [1,2,3,4]
输出：false
解释：序列中不存在 132 模式的子序列。

示例 2：

输入：nums = [3,1,4,2]
输出：true
解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。

示例 3：

输入：nums = [-1,3,2,0]
输出：true
解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。

 

提示：

• n == nums.length
• 1 <= n <= 2 * 105
• -109 <= nums[i] <= 109

方法一：单调栈 · Go 实现

思考

要找 $i<j<k$ 且 $nums[i]<nums[k]<nums[j]$。枚举三下标是 $O(n^3)$；枚举 $j$ 再左右扫描仍是 $O(n^2)$。

从右向左维护单调递减栈，并用 $vk$ 记录栈中弹出的、小于当前值的最大数，即目前最好的 $nums[k]$。当前值若小于 $vk$，它就可以当 $nums[i]$。

栈里是候选的 $nums[j]$（更大的峰）。先更新 $vk$ 再入栈，保证 $k$ 在 $j$ 右侧。

我们可以枚举从右往左枚举整数 $nums[i]$，并维护一个单调栈，栈中的元素从栈底到栈顶单调递减。维护一个变量 $vk$，表示 $nums[i]$ 右侧且小于 $nums[i]$ 的最大值。初始时， $vk$ 的值为 $-\mathrm{\infty }$。

我们从右往左遍历数组，对于遍历到的每个元素 $nums[i]$，如果 $nums[i]$ 小于 $vk$，则说明我们找到了一个满足 $nums[i]<nums[k]<nums[j]$ 的三元组，返回 true。否则，如果栈顶元素小于 $nums[i]$，则我们循环将栈顶元素出栈，并且更新 $vk$ 的值为出栈元素，直到栈为空或者栈顶元素大于等于 $nums[i]$。最后，我们将 $nums[i]$ 入栈。

如果遍历结束后仍未找到满足条件的三元组，说明不存在这样的三元组，返回 false。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组的长度。

func find132pattern(nums []int) bool {
	vk := -(1 << 30)
	stk := []int{}
	for i := len(nums) - 1; i >= 0; i-- {
		if nums[i] < vk {
			return true
		}
		for len(stk) > 0 && stk[len(stk)-1] < nums[i] {
			vk = stk[len(stk)-1]
			stk = stk[:len(stk)-1]
		}
		stk = append(stk, nums[i])
	}
	return false
}

方法二：离散化 + 树状数组 · Go 实现

思考

方法一线性，但依赖从右扫描的栈结构。也可以预处理左侧最小值，从右用树状数组查询「大于 $\mathit{\text{left}}[i]$ 且小于 $nums[i]$」是否出现过。

离散化后树状数组维护右侧已扫过的值。渐近多一个对数，实现成区间计数，不依赖单调栈。

我们可以用树状数组维护比某个数小的元素的个数，用一个数组 $left$ 记录 $nums[i]$ 左侧的最小值。

我们从右往左遍历数组，对于遍历到的每个元素 $nums[i]$，我们将 $nums[i]$ 离散化为一个整数 $x$，将 $left[i]$ 离散化为一个整数 $y$，如果此时 $x>y$，并且树状数组中存在比 $y$ 大但比 $x$ 小的元素，则说明存在满足 $nums[i]<nums[k]<nums[j]$ 的三元组，返回 true。否则，我们将 $nums[i]$ 的离散化结果 $x$ 更新到树状数组中。

如果遍历结束后仍未找到满足条件的三元组，说明不存在这样的三元组，返回 false。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组的长度。

type BinaryIndexedTree struct {
	n int
	c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
	c := make([]int, n+1)
	return &BinaryIndexedTree{n, c}
}

func (this *BinaryIndexedTree) update(x, val int) {
	for x <= this.n {
		this.c[x] += val
		x += x & -x
	}
}

func (this *BinaryIndexedTree) query(x int) int {
	s := 0
	for x > 0 {
		s += this.c[x]
		x -= x & -x
	}
	return s
}

func find132pattern(nums []int) bool {
	n := len(nums)
	s := make([]int, n)
	left := make([]int, n+1)
	left[0] = 1 << 30
	copy(s, nums)
	sort.Ints(s)
	m := 0
	for i := 0; i < n; i++ {
		left[i+1] = min(left[i], nums[i])
		if i == 0 || s[i] != s[i-1] {
			s[m] = s[i]
			m++
		}
	}
	s = s[:m]
	tree := newBinaryIndexedTree(m)
	for i := n - 1; i >= 0; i-- {
		x := sort.SearchInts(s, nums[i]) + 1
		y := sort.SearchInts(s, left[i]) + 1
		if x > y && tree.query(x-1) > tree.query(y) {
			return true
		}
		tree.update(x, 1)
	}
	return false
}

力扣原题 · Doocs 题解来源

475. 供暖器

中等1 种解法

标签：数组、双指针、二分查找、排序

题目、示例与约束

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

在加热器的加热半径范围内的每个房屋都可以获得供暖。

现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。

注意：所有供暖器 heaters 都遵循你的半径标准，加热的半径也一样。

 

示例 1:

输入: houses = [1,2,3], heaters = [2]
输出: 1
解释: 仅在位置 2 上有一个供暖器。如果我们将加热半径设为 1，那么所有房屋就都能得到供暖。

示例 2:

输入: houses = [1,2,3,4], heaters = [1,4]
输出: 1
解释: 在位置 1, 4 上有两个供暖器。我们需要将加热半径设为 1，这样所有房屋就都能得到供暖。

示例 3：

输入：houses = [1,5], heaters = [2]
输出：3

 

提示：

• 1 <= houses.length, heaters.length <= 3 * 104
• 1 <= houses[i], heaters[i] <= 109

方法一 · Go 实现

思考

加热器覆盖半径要覆盖所有房子，求最小半径。枚举半径再检查， $n$ 与坐标都大，但可行性关于半径单调。

排序后二分半径 $r$：双指针让每个加热器覆盖 $[h-r,h+r]$，房子落在左侧则失败，落在右侧则换下一个加热器。

房子与加热器都有序，指针只前进，一次检查是线性的。

func findRadius(houses []int, heaters []int) int {
	sort.Ints(houses)
	sort.Ints(heaters)
	m, n := len(houses), len(heaters)

	check := func(r int) bool {
		var i, j int
		for i < m {
			if j >= n {
				return false
			}
			mi, mx := heaters[j]-r, heaters[j]+r
			if houses[i] < mi {
				return false
			}
			if houses[i] > mx {
				j++
			} else {
				i++
			}
		}
		return true
	}
	left, right := 0, int(1e9)
	for left < right {
		mid := (left + right) >> 1
		if check(mid) {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

力扣原题 · Doocs 题解来源

483. 最小好进制

困难1 种解法

标签：数学、二分查找

题目、示例与约束

以字符串的形式给出 n , 以字符串的形式返回 n 的最小 好进制  。

如果 n 的  k(k>=2) 进制数的所有数位全为1，则称 k(k>=2) 是 n 的一个 好进制 。

 

示例 1：

输入：n = "13"
输出："3"
解释：13 的 3 进制是 111。

示例 2：

输入：n = "4681"
输出："8"
解释：4681 的 8 进制是 11111。

示例 3：

输入：n = "1000000000000000000"
输出："999999999999999999"
解释：1000000000000000000 的 999999999999999999 进制是 11。

 

提示：

• n 的取值范围是 [3, 1018]
• n 没有前导 0

方法一：Go 实现（halfrost） · Go 实现

halfrost · 源码 · MIT 许可

本次根据原始 Go 源码整理的中文说明，非 halfrost 书籍原文。

把输入十进制字符串转为整数，从较大的最高幂 m 向下枚举。源码用浮点开方估计候选进制 k，再逐项计算 1+k+…+k^m 并核对总和；没有命中时返回 n−1，对应表示 11。此说明描述现有实现，没有添加相邻候选检查或新的求根算法。

import (
	"math"
	"math/bits"
	"strconv"
)

func smallestGoodBase(n string) string {
	nVal, _ := strconv.Atoi(n)
	mMax := bits.Len(uint(nVal)) - 1
	for m := mMax; m > 1; m-- {
		k := int(math.Pow(float64(nVal), 1/float64(m)))
		mul, sum := 1, 1
		for i := 0; i < m; i++ {
			mul *= k
			sum += mul
		}
		if sum == nVal {
			return strconv.Itoa(k)
		}
	}
	return strconv.Itoa(nVal - 1)
}

力扣原题 · Doocs 题解来源