设计网站公司,网站建设方案范文2000字,备案 网站负责人 法人,工信部网站备案举报Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk
(๑•́ ₃ •̀๑) 文章专栏#xff1a; 算法Journey 本篇博客我们继续来了解一些有关二分查找算法的进阶题目。 #x1f3e0; 寻找峰值
#x1f4cc; 题目内容 162. 寻找峰值 - 力扣#… Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk
(๑•́ ₃ •̀๑) 文章专栏 算法Journey 本篇博客我们继续来了解一些有关二分查找算法的进阶题目。 寻找峰值 题目内容 162. 寻找峰值 - 力扣LeetCode 题目解析
与山脉数组那道题不同的是本题数组内存在多个峰值。注意本题一个规定即num[-1] num[n] 负无穷数组边界都是最小负无穷。
算法原理 思路一暴力解法 有三种情况下某个数是峰值我们暴力解法只需要遍历一遍数组进行分类情况即可但是时间复杂度是O(N)不符合题意。 思路二二分查找 我们发现 1. 当arr[i] arr[i1]时此时左边区域一定存在峰值因此我们要向左缩小范围。 2.当arr[i] arr[i1]时此时右边区域一定存在峰值因此我们要向右缩小范围。 3.由于峰值位置的不确定我们需要寻找峰值因此在寻找峰值的过程中我们发现了二段性因此可以使用二分查找。 二分过程 1. arr[i] arr[i1] --- right mid , 此时mid处可能就是峰值所以不能跳过mid。 2. arr[i] arr[i1] --- left mid 1 ,此时mid1处才可能是峰值因此可以跳过mid。 参考代码
class Solution
{public:int findPeakElement(vectorint nums) {int left 0;int right nums.size()-1;while(left right){int mid left (right - left ) / 2;if( nums[mid] nums[mid1]){left mid 1 ;}elseright mid;}return left;}}; 寻找旋转排序数组中的最小值 题目内容 153. 寻找旋转排序数组中的最小值 - 力扣LeetCode 题目内容
注意题目数组中的数字各不相同。 算法原理 思路一暴力解法 暴力解法思路很简单可以定义一个min变量遍历一遍数组遇到比他小的就更新min,时间复杂度是O(N),并不符合题目要求。 思路二二分查找 题目要我们找旋转排序数组中的最小值这个位置是“确定”的整个数组的大小变化趋势如上图。以D为参考点我们发现 1. 最小值所在位置的左边都是严格大于等于数组最后一个数的。 2.最小值所在位置的右边都是小于等于数组最后一个数的。 3.本题要我们求的很明显地划分了两段区间体现了二段性我们要做的是思考如果mid落在划分的两段区间内我们如何靠近目标。 二分流程 1. 当nums[mid] nums[n-1]时说明mid处于AB段此时我们需要向右缩小范围left mid1. 2.当nums[mid] nums[n-1]时说明mid位于CD段此时我们需要向左缩小范围由于目标在CD段上因此更新right时我们不能跳过mid因为mid可能就是最小值。 参考代码
class Solution {
public:int findMin(vectorint nums) {int left 0;int right nums.size() - 1;while(left right){int mid left (right - left) / 2;if(nums[mid] nums[right])right mid;else left mid1;}return nums[left]; }};
思考我们划分两端区间是以D为参考点那么我们是否能以A为参考点呢 1. A~B段是大于等于nums[0](A点)的而C~D段是严格小于nums[0]的。 2.此时二分流程 A - B : nums[i]nums[0] -- left mid 1; C - D : nums[i] nums[0] -- right mid; 3.当旋转数组旋转到原来升序时 此时A点就是最小值区间不断向右此时就会丢掉最小值因此对于这种边界情况我们需要特殊处理。 class Solution {
public:int findMin(vectorint nums) {int left 0;int right nums.size() - 1;if(nums[0] nums[right])return nums[0];int x nums[0]; //以A为参照while(left right){int mid left (right - left) / 2;if(nums[mid] x )left mid 1;else right mid;}return nums[left]; }}; 0~n-1中缺失的数字 题目内容 LCR 173. 点名 - 力扣LeetCode 题目内容
注意对于[0,1,2,3,4]这样的数组此时缺失的数字应该为5.
算法原理 思路一哈希表 由于缺了一个数字因此总的人数为数组元素个数1此时我们先遍历一遍数组进行映射再从0-N遍历没有映射的就是缺失的数字。 class Solution {
public:int takeAttendance(vectorint records) {unordered_mapint,int mp;for(const auto e : records){mp[e];}int reasult 0;int n records.size() 1; for(int i 0 ; i n ; i ){if(mp[i] 0){reasult i;break;}}return reasult;}
}; 思路二直接遍历找结果 由于学号从0开始因此数组中每个数都应该与下标相同由于缺失了一个数可能导致它的下一个数占它的位置也可能他就是最后一个数。 class Solution {
public:int takeAttendance(vectorint records) {bool flag false;int i 0;for( i 0 ; i records.size();i){if(i ! records[i]){flag true;break;}}return i;}
}; 思路三位运算 既然知道应到同学的人数n又根据按位异或a^a 0 的性质我们可以用ret遍历一遍数组进行异或再从0-N异或最后ret就是缺失的数字。 class Solution {
public:int takeAttendance(vectorint records) {int n records.size();int sum 0;for(int i 0 ;i n ;i){sum ^ i;}for(int i 0; i records.size();i){sum ^ records[i];}return sum;}
}; 思路四高斯求和公式 由于我们知道了应到学生人数因此我们可以用等差数列求原本应该的学号之和再遍历数组减去最后得到的就是缺失的数字。 class Solution {
public:int takeAttendance(vectorint records) {int n records.size() 1;int sum 0 (n*(n-1)) / 2;cout sum endl;for(int i 0; i records.size();i){sum - records[i];}return sum;}
} 思路五二分查找
前面的思路都很简单但时间复杂度都是O(N)。仔细观察我们发现因为缺失了数字会造成二段性。 我们发现由于缺失了一个数字造成了二段性 1. 左边一段区间的值都与下标相同而右边一段区间的值与下标不匹配因此我们需要去靠近第一个不与下标匹配的值。此时这个值的下标就是缺失的数字。 2.nums[mid] mid时说明mid在左边此时需要向右缩小范围。 3.nums[mid] ≠ mid时说明mid在右边此时mid可能就是我们要找的因此不能跳过mid. 4.需要注意的是对于类似[0,1,2,3,4]这样的情况最后leftright时我们需要返回left1. 参考代码
class Solution {
public:int takeAttendance(vectorint records) {int left 0;int right records.size() - 1;while(left right){int mid left (right - left ) / 2;if(records[mid] mid)left mid 1;elseright mid; }if(records[left] ! left) return left;return left 1; }
}; 总结 1. 当题目很明确要求的目标能划分二段性时我们需要考虑的是在划分区间内怎么接近目标。 2.当不是很明确二段性时我们要考虑的是在找目标的过程中能否发现二段性。
