当前位置：首页 > news >正文

L53.【LeetCode题解】二分法习题集2

news 来源：原创 2025/7/1 18:00:28

1.162. 寻找峰值

分析

代码

提交结果

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

分析

图像的增长趋势可以分这样几类

逐个击破

比较明显的

先增后减再增

用二段性给出left和right的更新算法

代码

提交结果

其他做法

提交结果

3.LCR 173. 点名(同剑指offer 53:0~n-1中缺失的数字)(一题多解)

分析

代码

提交结果

二分法的其他解法

其他解法1:异或运算

其他解法2:高斯求和

1.162. 寻找峰值

https://leetcode.cn/problems/find-peak-element/description/

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

给你一个整数数组 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
-2^31 <= nums[i] <= 2^31 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]

分析

假设 nums[-1] = nums[n] = -∞(这个是关键条件,后面会用到),例如nums=[1,2,3,1],其峰值元素为3,从图中看,类似于极大值点

又如nums=[1,2,1,3,5,6,4], 其峰值元素为2或6

暴力查找需要从左往右一个一个筛选,时间复杂度为 $O(N)$ ,运行速度慢,利用二段性,采用二分法,比较nums[i]和nums[i+1]的大小,有且仅有两种局部单调情况(nums[i]!=nums[i+1])

目标:寻找峰值一定存在的位置

1. nums[i]<nums[i+1]

i+1及i+1之后一定存在峰值元素,i之前可能没有峰值

2.nums[i]>nums[i+1]

i及i之前一定存在峰值元素,i+1之后可能没有峰值

显然只考虑"一定存在"的情况,根据nums[i]和nums[i+1]之间的大小关系来更新查找的区间:

当nums[mid]<nums[mid+1]时,更新区间为:left=mid+1

当nums[mid]>nums[mid+1]时,更新区间为:right=mid

代码

class Solution {
public:int findPeakElement(vector<int>& nums) {int left=0;int right=nums.size()-1;while (left<right){int mid=left+(right-left)/2;if (nums[mid]<nums[mid+1])left=mid+1;else//nums[mid]>nums[mid+1]right=mid;}return left;   }
};

注意:使用的是CC54.【C++ Cont】二分查找的左、右边界模版文章的查找左边界的模版, mid=left+(right-left)/2;不要写成 mid=left+(right-left+1)/2;,会死循环

提交结果

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

已知一个长度为 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 次旋转

分析

以[3,4,5,1,2]为例分析所有可能的旋转数组,分别画出它们的增长图:

[1,2,3,4,5]:

[5,1,2,3,4]:

[4,5,1,2,3]:

[3,4,5,1,2]:

[2,3,4,5,1]:

图像的增长趋势可以分这样几类

1.一直增: [1,2,3,4,5]

2.先减后增: [5,1,2,3,4]

3.先增后减再增: [4,5,1,2,3]、[3,4,5,1,2]

4.先增后减: [2,3,4,5,1]

逐个击破

比较明显的

先减后增特征明显:只有它上来先减,最小值在nums[1](前提:n>=2)

先增后减特征明显:只有它是最后减,最小值在nums[nums.size()-1](前提:n>=2)

先增后减再增

可以看出:最小值在左单增区间和右单增区间之间

给定初始区间[left,right],设计二分法让循环结束时,left==right==最小值所处的位置,

用二段性给出left和right的更新算法

观察可知:

如果i在左单增区间,那么nums[i]>nums[nums.size()-1](前提:n>=2)

如果i在右单增区间,那么nums[i]<=nums[nums.size()-1](前提:n>=2)

那么有:

当nums[mid]>nums[nums.size()-1]时,left=mid+1

当nums[mid]<=nums[nums.size()-1]时,right=mid

以上算法对于一直增的情况同样适用,因为一直满足nums[mid]<=nums[nums.size()-1],right=mid,区间右边界向左侧移动,最终left=right=0

*注:使用nums[0]来分左右单增区间见下面的其他方法

代码

class Solution {
public:int findMin(vector<int>& nums) {if (nums.size()==1)return nums[0];//先减后增if (nums[1]<nums[0])return nums[1];//先增后减if (nums[nums.size()-1]<nums[nums.size()-2])return nums[nums.size()-1];//一直增和先增后减再增int left=0;int right=nums.size()-1;while (left<right){int mid=left+(right-left)/2;if (nums[mid]>nums[nums.size()-1])//是否为左单增区间left=mid+1;else //否则为右单增区间: nums[mid]<=nums[nums.size()-1]right=mid;}return nums[left];}
};

提交结果

其他做法

如果用nums[0]来界定i在左单增区间还是右单增区间,写法是怎样的?

如果i在左单增区间,那么nums[i]>=nums[0](前提:n>=2)

如果i在右单增区间,那么nums[i]<nums[0](前提:n>=2)

该算法对一直增的情况是不能得出最小值的,left指针会一直向右移动,导致循环退出时,left和right都指向最大值,left==right==nums.size()-1(对于先增后减再增,循环结束时left和right是不可能等于nums.size()-1),此时只需要返回nums[0]即可

class Solution {
public:int findMin(vector<int>& nums) {if (nums.size()==1)return nums[0];//先减后增if (nums[1]<nums[0])return nums[1];//先增后减if (nums[nums.size()-1]<nums[nums.size()-2])return nums[nums.size()-1];//一直增和先增后减再增int left=0;int right=nums.size()-1;while (left<right){int mid=left+(right-left)/2;if (nums[mid]>=nums[0])//是否为左单增区间left=mid+1;else //否则为右单增区间: nums[mid]<nums[0]right=mid;}if (left==nums.size()-1)return nums[0];//一直增返回的结果elsereturn nums[left];//先增后减再增返回的结果}
};

提交结果

3.LCR 173. 点名(同剑指offer 53:0~n-1中缺失的数字)(一题多解)

https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/

某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。

示例 1：
输入：records = [0,1,2,3,5]
输出：4
示例 2：
输入：records = [0, 1, 2, 3, 4, 5, 6, 8]
输出：7
提示：

1 <= records.length <= 10000

分析

暴力解法显然是方法1:从左向右或者从右向左遍历,时间复杂度为 $O(N)$ ,可以使用二分法,观察是否具有二段性方法2:建哈希表,之后一个一个查

以0~(5-1)为例,分类讨论各个情况:

缺0: [1,2,3,4,5]

缺1: [0,2,3,4,5]

缺2: [0,1,3,4,5]

缺3: [0,1,2,4,5]

缺4: [0,1,2,3,5]

缺5: [0,1,2,3,4]

除了"缺0"和"缺5"的情况,其他情况均可以使用二段性进行分两段:

第一段:左单增段第二段:右单增段

以缺3: [0,1,2,4,5]的为例:

给一个指针i,通过看斜率来看在哪个区间

1.如果i在左单增区间,records[i]和records[records.size()-1]的连线的斜率是大于1的,即records[records.size() - 1] - records[mid] > records.size() - 1 - mid

此时更新left = mid

2.如果i在右单增区间,records[i]和records[0]的连线的斜率是大于1的,即records[mid] - records[0] > mid - 0

此时更新right = mid - 1

如果是"缺0"或者"缺5"的情况,那么情况1和2的斜率是一样的,这个特殊情况应该在首先就判断或者在最后返回的时候判断

代码

class Solution {
public:int takeAttendance(vector<int>& records){//mid==0if (records[records.size() - 1] - records[0] == records.size() - 1 - 0){if (records[0]==1)return 0;elsereturn records[records.size() - 1]+1;}int left = 0;int right = records.size() - 1;while (left < right){int mid = left + (right - left + 1) / 2;//左斜率:(nums[mid]-nums[0])/(mid-0)if (records[mid] - records[0] > mid - 0)//左斜率>1right = mid - 1;if (records[records.size() - 1] - records[mid] > records.size() - 1 - mid)left = mid;}return records[left] + 1;}
};

提交结果

二分法的其他解法

观察下标和元素之间的大小关系,以[0,1,3,4,5]为例

具有明显的二段性:

(最终返回下标2)

绿框中元素的值==下标,蓝框中元素的值==下标+1

分情况更新left和right即可,循环退出时返回下标即可

注意讨论特殊情况:缺5: [0,1,2,3,4],返回records.size(),这个必须一开始就判断或者在最后返回的时候判断

class Solution {
public:int takeAttendance(vector<int>& records){if (records[records.size()-1]==records.size()-1)return records.size();int left = 0;int right = records.size() - 1;while (left < right){int mid = left + (right - left) / 2;if (records[mid]==mid)//左斜率>1left = mid+1;elseright=mid;          }return left;}
};

提交结果:

其他解法1:异或运算

构造完整的数组与records数组异或,直接得出结果(这个解法之前在E24.【C语言】练习：求一个整数存储在内存中的二进制中1的个数（两种方法）文章中提到过)

class Solution {
public:int takeAttendance( vector<int>& records){int ret=0;for (int i=0;i<records.size();i++)ret^=records[i];for (int j=0;j<=records.size();ret^=j,j++);return ret;}
};

时间复杂度为 $O(N)$

提交结果:

其他解法2:高斯求和

class Solution {
public:int takeAttendance(vector<int>& records){int sum=0;for (int i=0;i<records.size();i++)sum+=records[i];return (0+records.size())*(records.size()+1)/2-sum;}
};

时间复杂度为 $O(N)$

提交结果:

1.162. 寻找峰值

分析

代码

提交结果

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

分析

图像的增长趋势可以分这样几类

逐个击破

比较明显的

先增后减再增

用二段性给出left和right的更新算法

代码

提交结果

其他做法

提交结果

3.LCR 173. 点名(同剑指offer 53:0~n-1中缺失的数字)(一题多解)

分析

代码

提交结果

二分法的其他解法

其他解法1:异或运算

其他解法2:高斯求和

相关文章：