Kydaa
1
第四期来啦。本期主题是很常见的二分查找，也是一个很重要的数据结构。二分查找简单点说就是从有序的序列中通过不断的二分缩小查找范围，最终查找到我们想要的目标数据。
本期为期一个月（春节休息一周），每周一三五早上八点半左右更新。
第一周
先掌握最基本的最原始的二分查找吧
如果存在重复元素，该怎么找到重复元素的最左和最右值？
把数组换成矩阵呢？看看自己是不是真的活学活用二分
第二周
上周的二分算法适用于一个有序数组，对于无序数组竟然也可以使用二分，那二分的判断条件怎么定？
给定数组并非有序，但查找判定条件有序，所以可以二分。
还是有人不能灵活使用二分，那就再来一道和上一题类似的吧
第三周
Tips:双重二分
一题多解的好题，很值得一做。
最后一题，来道hrad吧
参考资料
使用golang自带的二分搜索（可以直接看源码实现）
func search(nums []int, target int) int {
// index:= sort.Search(len(nums), func(i int) bool { return nums[i] >= target })
index:= sort.SearchInts(nums,target)
if index >= len(nums) || nums[index] !=target{
return -1
}
return index
}
2 个赞
打卡，704. 二分查找
虽然简单，二分还是要注重写对细节，没能一次性写完通过，改了一小下
class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.size() == 0) {
return -1;
}
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid - 1; // 注意 mid - 1
} else if (nums[mid] < target) {
left = mid + 1; // 注意 mid + 1
} else {
return mid;
}
}
return -1;
}
};
func search(nums []int, target int) int {
idx := sort.SearchInts(nums, target)
if idx >= len(nums) || nums[idx] != target {
return -1
}
return idx
}
之前用过好多次 go 标准库的 binary_search 操作，今天写了下还是忘了，其实后来一看标准库实现是一个 “升序 lower_bound 操作” 。。。
直接使用库函数
func searchRange(nums []int, target int) []int {
left := sort.SearchInts(nums, target) // 查询最左边比>= target的数。
if left == len(nums) || nums[left]!=target { // 有可能不等需要判断
return []int{-1,-1}
}
right := sort.SearchInts(nums, target+1) // 查询target最右边的右边一个位置。
return []int{left,right-1} // 这里要减1
}
1 个赞
[ 在排序数组中查找元素的第一个和最后一个位置](力扣)
// 我是抄楼上的
func searchRange(nums []int, target int) []int {
idx := sort.SearchInts(nums, target)
if idx >= len(nums) || nums[idx] != target {
return []int{-1, -1}
}
return []int{idx, sort.SearchInts(nums, target+1) - 1}
}
// 力扣
// 由于二分专题就用二分法来求解吧
// 实际上矩阵大小 100 * 100 完全没有必要用二分
func searchMatrix(matrix [][]int, target int) bool {
n, m := len(matrix), len(matrix[0])
if matrix[n-1][m-1] < target || matrix[0][0] > target {
return false
}
row := sort.Search(n, func(idx int) bool {
return matrix[idx][0] >= target
})
if row < n && matrix[row][0] == target {
return true
}
row--
col := sort.SearchInts(matrix[row], target)
if col >= m || matrix[row][col] != target {
return false
}
return true
}
周五： 74. 搜索二维矩阵
/*
将二维矩阵看成是一维的 arr = append(matrix[0], matrix[1]... matrix[n-1]
相互转化工式：matrix[i][j] = arr[i*m+j]
arr[x] = matrix[x/m][x%m]
*/
func searchMatrix(matrix [][]int, target int) bool {
n,m := len(matrix) ,len(matrix[0])
ind := sort.Search(n*m, func(x int) bool {
row, col := x/m, x%m
return matrix[row][col]>=target
})
return ind<n*m && matrix[ind/m][ind%m]==target
}
1 个赞
[34] 在排序数组中查找元素的第一个和最后一个位置
转换题目，求区间 [target, target+1) 的下标
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int left = lowerBound(nums, target);
int right = lowerBound(nums, target + 1) - 1;
if (right < nums.size() && nums[right] == target) {
return {left, right};
}
return {-1, -1};
}
// 求小于等于 target 的左下标
int lowerBound(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
right = mid - 1; // 还是一步一步缩短范围
}
}
return left;
}
};
[74] 搜索二维矩阵
参考上面 [LightningBilly] 同学的题解
/*
将 n * m 二维矩阵看成是一维的 arr = [ matrix[0], matrix[1]... matrix[n-1] ]
相互转化工式：matrix[i][j] = arr[i * m + j]
arr[x] = matrix[x / m][x % m]
*/
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.size() == 0 || matrix[0].size() == 0) {
return false;
}
int n = matrix.size();
int m = matrix[0].size();
int left = 0, right = n * m - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int midVal = matrix[mid / m][mid % m];
if (midVal < target) {
left = mid + 1;
} else if (midVal > target) {
right = mid - 1;
} else {
return true;
}
}
return false;
}
};
周一
func search(nums []int, target int) int {
left, rigth := 0, len(nums)-1
for left < rigth {
mid := (left+rigth)>>1
if nums[mid] >= target {
rigth = mid
}else {
left = mid+1
}
}
if nums[left] == target {
return left
}
return -1
}
周三
func searchRange(nums []int, target int) []int {
res := []int{-1,-1}
left, rigth := 0, len(nums)-1
for left < rigth {
mid := (left+rigth) >> 1
if nums[mid] >= target {
rigth = mid
}else {
left = mid+1
}
}
if nums[left] == target {
res[0] = left
}
left, rigth = 0, len(nums)-1
for left < rigth {
mid := (left+rigth+1) >> 1
if nums[mid] <= target {
left = mid
}else {
rigth = mid-1
}
}
if nums[rigth] == target {
res[1] = rigth
}
return res
}
func findPeakElement(nums []int) int {
low, high := 0, len(nums)-1
best := -1 // 默认无解，也可以根据需要置其他特殊值
for low <= high {
mid := low + (high-low)/2
if mid == 0 {
if mid+1 == len(nums) || nums[mid] > nums[mid+1] {
best = mid
break
}
best, low = mid+1, mid+1
} else if mid == len(nums)-1 {
if nums[mid-1] < nums[mid] {
best = mid
break
}
best, high = mid-1, mid-1
} else if nums[mid-1] < nums[mid] && nums[mid] > nums[mid+1] {
best = mid
break
} else if nums[mid-1] < nums[mid] {
best, low = mid, mid+1
} else if nums[mid-1] > nums[mid] {
best, high = mid-1, mid-1
}
}
return best
}
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int i,l=nums.size();
for(i=0;i<l;i++)
{
if(i && nums[i-1]>=nums[i])continue;
if(i<l-1 && nums[i]<=nums[i+1])continue;
return i;
}
return 0;
}
};
常规二分做法：
func findPeakElement(nums []int) int {
low :=0
high := len(nums)
for low < high {
middle := (low + high)/2
if middle >0 && nums[middle] > nums[middle-1]{
low = middle+1
}else {
high = middle
}
}
if low ==0{
return low
}
return low-1
}
提升：三分做法，三分法可以用来查找凸函数的最大（小）值。详见wiki
func findPeakElement(nums []int) int {
low :=0
high := len(nums)
for high-low>1 {
lmid := (low + high)/2
rmid := (lmid + high)/2 // 对右侧区间取半
if nums[lmid] >= nums[rmid]{
high = rmid
}else {
low = lmid
}
}
if high == len(nums) || nums[low] > nums[high]{ //由于本题存在假设边界不是完全的凸（凹）函数，需要做额外的判断
return low
}
return high
}
// 二分法
//func findPeakElement(nums []int) int {
// l, r := 0, len(nums)-1
// for l < r {
// mid := l + (r-l)/2
// if mid + 1 < len(nums) && nums[mid+1] > nums[mid] {
// l = mid + 1
// } else {
// r = mid
// }
// }
// return l
//}
难度困难231收藏分享切换为英文接收动态反馈
给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。
（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）
返回 A 中好子数组的数目。
思路
- 先求包含k个不同字符的最长区间
- 然后求固定右边界，包含k个不同字符的子数组个数
go
/*
* @Description:
* @Version: 2.0
* @Author: kingeasternsun
* @Date: 2021-02-09 17:58:29
* @LastEditors: kingeasternsun
* @LastEditTime: 2021-02-09 21:49:00
* @FilePath: /992subarraysWithKDistinct/992.go
*/
package leetcode
/*
类似 求和为特定value的子数组个数；滑窗加hash
*/
func subarraysWithKDistinct(A []int, K int) int {
res := 0
cntMap := make(map[int]int, 0)
//其实这一步可以省略 也不影响最终的结果
for i := 0; i < K; i++ {
cntMap[A[i]]++
}
// 左闭 右闭 区间 [left, right]
left := 0
right := K - 1
for left <= right {
if len(cntMap) <= K {
if len(cntMap) == K {
res += help(A, left, right, cntMap, K)
}
if right+1 == len(A) {
return res
}
//向右移动
right++
cntMap[A[right]]++
} else if len(cntMap) > K {
cntMap[A[left]]--
if cntMap[A[left]] == 0 {
delete(cntMap, A[left])
}
left++
}
}
return res
}
// 计算以right为结尾的满足条件的子数组有多少个
func help(A []int, left, right int, cntMap map[int]int, K int) int {
tmpMap := make(map[int]int, 0) //记录移除的个数，这样就不会改变原有的cntMap
cnt := 0
for left <= right {
cnt++
//移动left
tmpMap[A[left]]++
if tmpMap[A[left]] == cntMap[A[left]] {
break
}
left++
}
return cnt
}