爱好摄影一枚程序媛~~
二分法使用场景:前提是排好序的数组,看到排好序的应该有使用二分法的想法。使用的时候,要知道二分法的作用是可以更快速的找出符合条件的值。时间复杂度为
,而全局遍历会使用
的时间
二分法使用方法:三个变量决定一切。x,y,mid 分别表示数组的左边界、右边界、中间值。使用中间值,来计算下一次遍历的数组是左子数组还是右子数组。
如下图:
我们知道了二分法的使用场景之后,看一个例子(注:本文代码均为Golang语言)
一、题目描述
LeetCode-53.0~n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。
示例 1:
输入: [0,1,3] 输出: 2 示例 2:
输入: [0,1,2,3,4,5,6,7,9] 输出: 8
二、思路分析
分析:数组是有序数列,考虑使用二分法。
怎么使用:首先分析题目,下标与对应的值应一致,第一个不一致的值就是我们要找的值。怎么找不一致的值,我们可以把数组一分为二去寻找。
三、AC代码
func missingNumber(nums []int) int {
lenNum := len(nums)
var i, j, m int
j = lenNum - 1
for i <= j {
if nums[0] != 0 { // 特殊值
return 0
}
m = (i + j) / 2 // 取中间值
if nums[m] == m { // 若中间值==其下标 说明数组的左部分是OK的,那么不一致的值就在右部分
i = m + 1 // i的值变更
} else { // 若中间值!=其下标 说明数组的左部分出现了不一致的情况,开始遍历左部分
j = m - 1 // j的值变更
}
}
return i
}
四、总结
本题为easy难度,其实从一个简单的题目可以能感觉出二分法的意义。不如,再练中等题目试一试
同系列题目
- LeetCode-275.H指数【难度:中等】
示例:
输入: citations = [0,1,3,5,6] 输出: 3 解释: 给定数组表示研究者总共有 5 篇论文,每篇论文相应的被引用了 0, 1, 3, 5, 6 次。 由于研究者有 3 篇论文每篇至少被引用了 3 次,其余两篇论文每篇被引用不多于 3 次,所以她的 h 指数是 3。
提示:
设定 h=n-i对应被应用的文章数,a[i]对应的是引用次数。 则h <= a[i] 也即 n-i <= a[i]
func hIndex(citations []int) int {
lenCi := len(citations)
var i, j, mid, ans int
j = lenCi - 1
for i <= j {
mid = (i + j) / 2
h := lenCi - mid
if h <= citations[mid] {
ans = h
j = mid - 1
} else {
i = mid + 1
}
}
return ans
}
- LeetCode-540.有序数组中的单一元素【难度:中等】
给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。
示例 1:
输入: [1,1,2,3,3,4,4,8,8] 输出: 2 示例 2:
输入: [3,3,7,7,10,11,11] 输出: 10
AC代码
func singleNonDuplicate(nums []int) int {
lenN := len(nums)
var i, j, mid int
j = lenN - 1
for i < j {
mid = (i + j) / 2
if mid%2 == 0 { // 一分为二后的元素是偶数个
if nums[mid] == nums[mid-1] { //
j = mid - 2
} else if nums[mid] == nums[mid+1] {
i = mid + 2
} else { // 中间值即为单一元素
return nums[mid]
}
} else { // 一分为二后的元素是奇数个
if nums[mid] == nums[mid-1] {
i = mid + 1
} else if nums[mid] == nums[mid+1] {
j = mid - 1
} else {
return nums[mid]
}
}
}
return nums[i]
}
- 本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情
今天的文章[二分法系列]|刷题打卡分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/17009.html