使用二分法来解决的一些问题
使用二分法来解决的一些问题
作者:Grey
原文地址:
在一个有序数组中,找某个数是否存在
在线测评见:LeetCode 704. Binary Search
思路:
-
由于是有序数组,可以先得到中点位置,中点可以把数组分为左右半边;
-
如果中点位置的值等于目标值,直接返回中点位置;
-
如果中点位置的值小于目标值,则去数组中点左侧按同样的方式寻找;
-
如果中点位置的值大于目标值,则取数组中点右侧按同样的方式寻找;
-
如果最后没有找到,则返回:-1。
代码
class Solution {
public int search(int[] arr, int t) {
if (arr == null || arr.length < 1) {
return -1;
}
int l = 0;
int r = arr.length - 1;
while (l <= r) {
int m = l + ((r - l) >> 1);
if (arr[m] == t) {
return m;
} else if (arr[m] > t) {
r = m - 1;
} else {
l = m + 1;
}
}
return -1;
}
}
时间复杂度 O(logN)
。
在一个有序数组中,找大于等于某个数最左侧的位置
在线测评见:LeetCode 35. Search Insert Position
示例 1:
输入: nums = [1,3,5,6]
, target = 5
输出: 2
说明:如果要在 num 这个数组中插入 5 这个元素,应该是插入在元素 3 和 元素 5 之间的位置,即 2 号位置。
示例 2:
输入: nums = [1,3,5,6]
, target = 2
输出: 1
说明:如果要在 num 这个数组中插入 2 这个元素,应该是插入在元素 1 和 元素 3 之间的位置,即 1 号位置。
示例 3:
输入: nums = [1,3,5,6]
, target = 7
输出: 4
说明:如果要在 num 这个数组中插入 7 这个元素,应该是插入在数组末尾,即 4 号位置。
通过上述示例可以知道,这题本质上就是求在一个有序数组中,找大于等于某个数最左侧的位置,如果不存在,就返回数组长度(表示插入在最末尾位置)
我们只需要在上例基础上进行简单改动即可,上例中,我们找到满足条件的位置就直接返回。
if (arr[m] == t) {
return m;
}
在本问题中,因为要找到最左侧的位置,
所以,
在遇到 arr[m] == t
的时候,不用直接返回,而是先把位置记录 m 下来,然后继续去左侧找是否还有满足条件的更左边的位置。
同时,
在遇到arr[m] > t
条件下,也需要记录下此时的 m 位置,因为这也可能是满足条件的位置。
代码:
class Solution {
public static int searchInsert(int[] arr, int t) {
int ans = arr.length;
int l = 0;
int r = arr.length - 1;
while (l <= r) {
int m = l + ((r - l)>>1);
if (arr[m] >= t) {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans;
}
}
整个算法的时间复杂度是O(logN)
。
在排序数组中查找元素的第一个和最后一个位置
OJ见:LeetCode 34. Find First and Last Position of Element in Sorted Array
思路
本题也是用二分来解,当通过二分找到某个元素的时候,不急着返回,而是继续往左(右)找,看能否找到更左(右)位置匹配的值。
代码如下:
class Solution {
public static int[] searchRange(int[] arr, int t) {
if (arr == null || arr.length < 1) {
return new int[]{-1, -1};
}
return new int[]{left(arr,t),right(arr,t)};
}
public static int left(int[] arr, int t) {
if (arr == null || arr.length < 1) {
return -1;
}
int ans = -1;
int l = 0;
int r = arr.length - 1;
while (l <= r) {
int m = l + ((r - l) >> 1);
if (arr[m] == t) {
ans = m;
r = m - 1;
} else if (arr[m] < t) {
l = m +1;
} else {
// arr[m] > t
r = m - 1;
}
}
return ans;
}
public static int right(int[] arr, int t) {
if (arr == null || arr.length < 1) {
return -1;
}
int ans = -1;
int l = 0;
int r = arr.length - 1;
while (l <= r) {
int m = l + ((r - l) >> 1);
if (arr[m] == t) {
ans = m;
l = m + 1;
} else if (arr[m] < t) {
l = m +1;
} else {
// arr[m] > t
r = m - 1;
}
}
return ans;
}
}
时间复杂度O(logN)
。
局部最大值问题
OJ见:LeetCode 162. Find Peak Element
思路
假设数组长度为 N ,首先判断 0 号位置的数和 N-1 号位置的数是不是峰值位置。
0 号位置只需要和 1 号位置比较,如果 0 号位置大, 0 号位置就是峰值位置,可以直接返回。
N-1 号位置只需要和 N-2 号位置比较,如果 N-1 号位置大, N-1 号位置就是峰值位置,可以直接返回。
如果 0 号位置和 N-1 在上轮比较中均是最小值,那么数组的样子必然是如下情况:
由上图可知,0 到 1 这段是增长趋势, N-2 到 N-1 这段是下降趋势。
那么峰值位置必在[1...N-2]
之间出现。
此时可以通过二分来找峰值位置,先来到中点位置,假设中点为 mid ,如果中点位置的值比左右两边的值都大,即:
arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1]
则 mid 位置即峰值位置,直接返回。
否则,有如下两种情况:
情况一:mid 位置的值比 mid - 1 位置的值小
趋势如下图:
则在[1...(mid-1)]
区间内继续上述二分。
情况二:mid 位置的值比 mid + 1 位置的值小
趋势是:
则在[(mid+1)...(N-2)]
区间内继续上述二分。
如果最后都没找到,返回 -1 即可。
由于题目已经说明:
对于所有有效的 i 都有nums[i] != nums[i + 1]
。
所以,不会有相邻相等的情况。
完整代码如下
public class LeetCode_0162_FindPeakElement {
public static int findPeakElement(int[] arr) {
if (arr == null || arr.length == 0) {
return -1;
}
if (arr.length == 1) {
return 0;
}
if (arr[1] < arr[0]) {
return 0;
}
if (arr[arr.length - 1] > arr[arr.length - 2]) {
return arr.length - 1;
}
int ans = -1;
int l = 1;
int r = arr.length - 2;
while (l <= r) {
int mid = l + ((r - l)>>1);
if (arr[mid] > arr[mid + 1] && arr[mid] > arr[mid-1]) {
return mid;
} else if (arr[mid] < arr[mid + 1]) {
l = mid + 1;
} else if (arr[mid] < arr[mid - 1]) {
r = mid - 1;
} else {
// 题目要求下,不会走到这个分支
}
}
return ans;
}
}
时间复杂度O(logN)
。
更多
相关文章
- ES6躬行记(15)——箭头函数和尾调用优化
- ES6躬行记(14)——函数
- ES6躬行记(13)——类型化数组
- 躁!DJ 风格 Java 桌面音乐播放器
- GitHub 热点速览 Vol.13:近 40k star 计算机论文项目再霸 GitHub Trending 榜
- C# WinForm 界面控件
- 前脚结束面试,后脚意向书就发来了。。。
- PHP 面向对象知识点
- 软件测试|selenium常用页面信息对比方法expected_conditions
- 学会这一招,快速自动计算各职级的薪酬分位值
- 一次安全厂商面试经历分享
- C/C++ 计算文件ROF再计算VAOF
- C/C++ 递归遍历文件并计算MD5
- LyScript 计算片段Hash并写出Excel
- 驱动开发:内核LDE64引擎计算汇编长度
- 参加面试前,一定要知道的互联网黑话
- 官宣!流计算开发管理框架 StreamPark 成功进入 Apache 孵化器
- Galaxy Release (v 22.05),新历史面板发布
- 页面加载代码
- Shell:变量数值计算(上)