qq教程网站源码,平面设计要用到哪些软件,wordpress 产品图片,可以免费学编程的网站【LeetCode刷题】Day 14 题目1#xff1a;153.寻找旋转排序数组中的最小值思路分析#xff1a;思路1#xff1a;二分查找#xff1a;以A为参照思路2#xff1a;二分查找#xff0c;以D为参照 题目2#xff1a;LCR 173.点名思路分析#xff1a;思路1#xff1a;遍历查找… 【LeetCode刷题】Day 14 题目1153.寻找旋转排序数组中的最小值思路分析思路1二分查找以A为参照思路2二分查找以D为参照 题目2LCR 173.点名思路分析思路1遍历查找思路2哈希表思路3异或思路4求和思路5二分查找 题目1153.寻找旋转排序数组中的最小值 思路分析 O(logN)来做我们就直接二分查找。所以第一步去寻找其中的二段性。 这里我们可以有两种方式以A为参照以D为参照来找C点的值。
思路1二分查找以A为参照 以A为参照 1. 二段性[A-B段都大于等于A][C-D段都小于A] 2. 迭代C点在left外所以leftmid1C在right内所以rightmid没有-1上面就不用1midleft(right-left)/2 特殊情况翻转后刚好是原来的升序数组此时以A为参照会把该数组当成全部A-B段会不断向外找直到leftright不成立而结束该情况需要特殊处理。 代码实现
class Solution {
public:int findMin(vectorint nums) {int left0,rightnums.size()-1;if(nums[left]nums[right]) return nums[left];while(leftright){int midleft(right-left)/2;if(nums[mid]nums[0]) leftmid1;else rightmid;}return nums[right];}
};思路2二分查找以D为参照 以C为参照 1. 二段性[A-B段都大于D][C-D段都小于等于D] 2. 迭代C点在left外所以leftmid1C在right内所以rightmid没有-1上面就不用1midleft(right-left)/2 无特殊情况若翻转后刚好是原来的升序数组会把整个数组当成C-D段以D为参照会往下找就可以找到C所以无需处理 代码实现
class Solution {
public:int findMin(vectorint nums) {int left0,rightnums.size()-1; while(leftright){int midleft(right-left)/2;if(nums[mid]nums[nums.size()-1]) leftmid1;else rightmid;}return nums[right];}
};LeetCode链接153.寻找旋转排序数组中的最小值 题目2LCR 173.点名 思路分析
这道题很简单有很多思路简单的我就直接讲一下过程就OK。
思路1遍历查找
遍历数组寻找后一位减前一位的差为2的数找到就返回没找到就返回最后一个数的下一个。
思路2哈希表
分别将数据导入哈希表然后查看哪个数的个数为零返回该值。
思路3异或
数组records[0]~records[size-1] 与 当前数组各个数异或若结果为x则返回x当x等于0时需要格外处理有两种情况缺0或者是最后一个数后面的数。需要特殊处理比对第一个数是不是0就可以。
思路4求和
数组records[0]~records[size-1] 的和减去当前数组的和。若结果为x则返回x当x等于0时需要格外处理与思路3一样。
思路5二分查找
这道题的二分查找很有趣需要细节能发现二段性这题就相当简单。我们可以发现这个升序数组是从0到n-1所以我们可以发现这样一个 二段性[缺失值前面下标与值相同][缺失值后面下标与值不同]我们找到右区间的左值的下标就是缺失的值。 细节处理当所有数的值和下标相同时则返回left1.
代码实现
class Solution {
public:int takeAttendance(vectorint records) {int left0,rightrecords.size()-1;while(leftright){int midleft(right-left)/2;if(midrecords[mid]) leftmid1;else rightmid;}//处理细节如果缺失的是最后一位if(leftrecords[left]) return left1;else return left;}
};LeetCode链接LCR 173.点名 世界舞台就是草台班子大胆尝试吧 ~天天开心
