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

本文主要是介绍【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【LeetCode刷题】Day 14

  • 题目1:153.寻找旋转排序数组中的最小值
    • 思路分析:
    • 思路1:二分查找:以A为参照
    • 思路2:二分查找,以D为参照
  • 题目2:LCR 173.点名
    • 思路分析:
    • 思路1:遍历查找
    • 思路2:哈希表
    • 思路3:异或
    • 思路4:求和
    • 思路5:二分查找

在这里插入图片描述

题目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上面就不用+1mid=left+(right-left)/2
特殊情况:翻转后刚好是原来的升序数组,此时以A为参照会把该数组当成全部A-B段,会不断向外找,直到left<right不成立而结束,该情况需要特殊处理。

代码实现:

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上面就不用+1mid=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.点名


世界舞台就是草台班子,大胆尝试吧!!! ~天天开心🎈
请添加图片描述

这篇关于【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1024020

相关文章

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int

vue如何监听对象或者数组某个属性的变化详解

《vue如何监听对象或者数组某个属性的变化详解》这篇文章主要给大家介绍了关于vue如何监听对象或者数组某个属性的变化,在Vue.js中可以通过watch监听属性变化并动态修改其他属性的值,watch通... 目录前言用watch监听深度监听使用计算属性watch和计算属性的区别在vue 3中使用watchE

Qt QWidget实现图片旋转动画

《QtQWidget实现图片旋转动画》这篇文章主要为大家详细介绍了如何使用了Qt和QWidget实现图片旋转动画效果,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 一、效果展示二、源码分享本例程通过QGraphicsView实现svg格式图片旋转。.hpjavascript

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig