【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名

简介: 【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名

题目1:153.寻找旋转排序数组中的最小值

思路分析:

O(logN)来做,我们就直接二分查找。所以第一步,去寻找其中的二段性。

这里我们可以有两种方式:以A为参照,以D为参照,来找C点的值。

思路1:二分查找:以A为参照

以A为参照:

1. 二段性:[A-B段都大于等于A][C-D段都小于A]

2. 迭代:C点在left外,所以left=mid+1,C在right内,所以right=mid,没有-1上面就不用+1,mid=left+(right-left)/2

特殊情况:翻转后刚好是原来的升序数组,此时以A为参照会把该数组当成全部A-B段,会不断向外找,直到left

代码实现:

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


思路2:二分查找,以D为参照

以C为参照:

1. 二段性:[A-B段都大于D][C-D段都小于等于D]

2. 迭代:C点在left外,所以left=mid+1,C在right内,所以right=mid,没有-1上面就不用+1,mid=left+(right-left)/2

无特殊情况:若翻转后刚好是原来的升序数组,会把整个数组当成C-D段,以D为参照,会往下找,就可以找到C,所以无需处理


代码实现:

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

LeetCode链接:153.寻找旋转排序数组中的最小值


题目2:LCR 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,所以我们可以发现这样一个

二段性:[缺失值前面,下标与值相同][缺失值后面,下标与值不同],我们找到右区间的左值的下标就是缺失的值。

细节处理:当所有数的值和下标相同时,则返回left+1.

代码实现:

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int left=0,right=records.size()-1;
        
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(mid==records[mid]) left=mid+1;
            else right=mid;
        }
        //处理细节:如果缺失的是最后一位
        if(left==records[left]) return left+1;
        else return left;
    }
};

LeetCode链接:LCR 173.点名

相关文章
|
23天前
|
索引
力扣随机一题 6/26 哈希表 数组 思维
力扣随机一题 6/26 哈希表 数组 思维
14 0
|
23天前
|
存储 算法 索引
力扣每日一题 6/24 模拟 数组 单调栈
力扣每日一题 6/24 模拟 数组 单调栈
9 0
|
23天前
力扣随机一题 哈希表 排序 数组
力扣随机一题 哈希表 排序 数组
11 1
|
23天前
|
存储 算法
力扣每日一题 6/20 数学+数组
力扣每日一题 6/20 数学+数组
16 1
|
11天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
19天前
2670.找出不同元素数目差数组-力扣(LeetCode)
2670.找出不同元素数目差数组-力扣(LeetCode)
8 0
|
23天前
|
算法 索引
力扣随机一题 位运算/滑动窗口/数组
力扣随机一题 位运算/滑动窗口/数组
16 0
|
23天前
|
算法 索引
力扣每日一题 6/28 动态规划/数组
力扣每日一题 6/28 动态规划/数组
19 0
|
23天前
力扣随机一题 6/28 数组/矩阵
力扣随机一题 6/28 数组/矩阵
15 0
|
23天前
|
存储 安全
力扣每日一题 6/21 数组
力扣每日一题 6/21 数组
9 0