【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数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

MySQL中查找重复值的实现

《MySQL中查找重复值的实现》查找重复值是一项常见需求,比如在数据清理、数据分析、数据质量检查等场景下,我们常常需要找出表中某列或多列的重复值,具有一定的参考价值,感兴趣的可以了解一下... 目录技术背景实现步骤方法一:使用GROUP BY和HAVING子句方法二:仅返回重复值方法三:返回完整记录方法四:

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

一文详解Java Stream的sorted自定义排序

《一文详解JavaStream的sorted自定义排序》Javastream中的sorted方法是用于对流中的元素进行排序的方法,它可以接受一个comparator参数,用于指定排序规则,sorte... 目录一、sorted 操作的基础原理二、自定义排序的实现方式1. Comparator 接口的 Lam

基于 HTML5 Canvas 实现图片旋转与下载功能(完整代码展示)

《基于HTML5Canvas实现图片旋转与下载功能(完整代码展示)》本文将深入剖析一段基于HTML5Canvas的代码,该代码实现了图片的旋转(90度和180度)以及旋转后图片的下载... 目录一、引言二、html 结构分析三、css 样式分析四、JavaScript 功能实现一、引言在 Web 开发中,

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

C++作用域和标识符查找规则详解

《C++作用域和标识符查找规则详解》在C++中,作用域(Scope)和标识符查找(IdentifierLookup)是理解代码行为的重要概念,本文将详细介绍这些规则,并通过实例来说明它们的工作原理,需... 目录作用域标识符查找规则1. 普通查找(Ordinary Lookup)2. 限定查找(Qualif

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序