【牛客网-面试必刷TOP101】二分查找题目
目录
二维数组中的查找_牛客题霸_牛客网 (nowcoder.com)
寻找峰值_牛客题霸_牛客网 (nowcoder.com)
数组中的逆序对_牛客题霸_牛客网 (nowcoder.com)
旋转数组的最小数字_牛客题霸_牛客网 (nowcoder.com)
二维数组中的查找_牛客题霸_牛客网 (nowcoder.com)
题意:
在一个二维数组array中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]]
给定 target = 7,返回 true。
给定 target = 3,返回 false。
数据范围:矩阵的长宽满足 0≤n,m≤5000 , 矩阵中的值满足 0≤val≤10^9
进阶:空间复杂度 O(1) ,时间复杂度 O(n+m)
【输入样例】7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
【输出样例】true
解题思路:
矩阵的规律是从左到右递增,从上到下递增。
选择矩阵的右上角a[row][col]进行对比,如果target<a[row][col],证明target在当前列的左边,我们可以往左边矩阵寻找;
如果target>a[row][col],证明target在当前行的下方,我们往下边矩阵寻找;
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param target int整型 * @param array int整型二维数组 * @return bool布尔型*/public boolean Find (int target, int[][] array) {// write code hereint n = array.length;int m = array[0].length;int row = 0;//行int col = m-1;//列while(row < n && col >= 0){if(target == array[row][col]){return true;}else if(target > array[row][col]){row++;}else{col--;}}return false;}
}
寻找峰值_牛客题霸_牛客网 (nowcoder.com)
题意:
给定一个长度为n的数组nums,请你找到峰值并返回其索引。数组可能包含多个峰值,在这种情况下,返回任何一个所在位置即可。
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
2.假设 nums[-1] = nums[n] = −∞
3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
4.你可以使用O(logN)的时间复杂度实现此问题吗?
数据范围:
1≤nums.length≤2×105
−231<=nums[i]<=231−1
输入样例:[2,4,1,2,7,8,4]
输出样例:1
解题思路:
1.暴力枚举,只要比上一位大并且比下一位大,就是峰值,直接返回
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param nums int整型一维数组 * @return int整型*/public int findPeakElement (int[] nums) {// write code hereif(nums.length >= 2 && nums[0] > nums[1] || nums.length == 1){return 0;}if(nums.length >= 2 && nums[nums.length-2] < nums[nums.length-1]){return nums.length-1;}for(int i=1;i<nums.length-1;++i){if(nums[i] > nums[i-1] && nums[i] > nums[i+1]){return i;}}return -1;}
}
解题思路2:
二分查找,实现时间复杂度为O(Logn)
跟普通的二分查找一样,先计算mid
如果nums[mid] > num[mid+1],说明mid很可能是峰值,我们往左遍历,这里与二分查找的区别是,往左时候right=mid,而不是mid-1,因为mid是可能的峰值取值,需要在下一轮遍历中进行比较;
如果nums[mid] <= nums[mid+1],则说明mid+1很可能是一个峰值,我们往右边进行遍历,left = mid+1,因为mid已经不是可能的峰值取值了,所以不包含
通过多轮的遍历,最终可以在区间里面找到一个正确的峰值。
如果是单调递增的话,每一次都往右走,直到left=right=nums.length-1;单调递减一直往左走,直到left=right=0
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param nums int整型一维数组 * @return int整型*/public int findPeakElement (int[] nums) {// write code hereif(nums.length == 1){return 0;}int left = 0;int right = nums.length -1;int mid;while(left < right){mid = (left + right) /2;if(nums[mid] > nums[mid+1]){//mid比下一位大,有可能是山峰,往左遍历right = mid;//注意这里right是赋值mid,因为mid可能是山峰,所以要包含他去寻找}else{//mid比它下一位小,mid+1有可能是山峰,向右走left = mid + 1;//从大的数开始往右查找}}return right;}
}
数组中的逆序对_牛客题霸_牛客网 (nowcoder.com)
题目描述:
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
数据范围: 对于 50% 的数据,size≤10^4
对于 100%的数据,size≤10^5数组中所有数字的值满足 0≤val≤10^9
要求:空间复杂度 O(n),时间复杂度 O(nlogn)
【输入样例】[1,2,3,4,5,6,7,0]
【输出样例】7
解题思路1:双重循环,暴力枚举,时间复杂度为O(n^2),运行超时
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param nums int整型一维数组 * @return int整型*/public int InversePairs (int[] nums) {// write code hereint ans=0;for(int i =0; i<nums.length-1; ++i){for(int j=i; j< nums.length; ++j){if(nums[i] > nums[j]){ans++;ans %= 1000000007;} }}return ans;}
}
解题思路2:
基于归并排序法,在合并时候,如果右边的数小于左边的数,可以直接求出当前产生的逆序对的个数。
import java.util.*;public class Solution {int ans=0;public int InversePairs (int[] nums) {// write code hereif(nums.length < 2){return 0;}mergeSort(nums,0,nums.length-1);return ans;}public void mergeSort(int[] nums,int left,int right){//分割点int mid = (left+right)/2;if(left < right){mergeSort(nums,left,mid);mergeSort(nums,mid+1,right);//合并merge(nums,left,mid,right);}}public void merge(int[] nums,int left,int mid,int right){//创建临时数组int[] arr = new int[right - left + 1];//临时数组下标起点int c = 0;int s = left;int l = left;int r = mid + 1;//左右数组的起始指针while(l <= mid && r <= right){//当左数组的元素小时,跳过if(nums[l] <= nums[r]){//放入临时数组arr[c] = nums[l];c++;l++;}else{//存在逆序对,统计arr[c] = nums[r];//逆序对个数,ans += mid+1 - l;ans %= 1000000007;c++;r++;}}//左子数组还有元素,放入while(l <= mid){arr[c++] = nums[l++];}while(r <= right){arr[c++] = nums[r++];}//临时数组放入数组原位置for(int num: arr){nums[s++] = num;}}
}
旋转数组的最小数字_牛客题霸_牛客网 (nowcoder.com)
题目描述:
有一个长度为 n 的非降序数组,比如[1,2,3,4,5],将它进行旋转,即把一个数组最开始的若干个元素搬到数组的末尾,变成一个旋转数组,比如变成了[3,4,5,1,2],或者[4,5,1,2,3]这样的。请问,给定这样一个旋转数组,求数组中的最小值。
数据范围:1≤n≤10000,数组中任意元素的值: 0≤val≤10000
要求:空间复杂度:O(1) ,时间复杂度:O(logn)
【输入样例】[3,4,5,1,2]
【输出样例】1
解题思路:
将一个非降序的数组进行旋转,我们利用二分查找,将数组划分为两个子数组时,肯定有一个子数组不是有序的;
如[left,right] 划分为[left,mid] [mid,right],如果nums[left] > nums[mid],证明 [left, mid]区间已经不符合非降序数组的要求了,所以这个区间旋转之后变成无序的,最小值在这里面寻找;
如果是相等,则缩小范围继续寻找
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param nums int整型一维数组 * @return int整型*/public int minNumberInRotateArray (int[] nums) {// write code hereint left = 0;int right = nums.length-1;while(left < right){int mid = (left + right) / 2;if(nums[mid] > nums[right]){ //右子数组无序left = mid + 1;}else if(nums[mid] < nums[right]){//左子数组无序right = mid;}else{//如果是相等的话,缩小范围right--;}}return nums[left];}
}
相关文章:
【牛客网-面试必刷TOP101】二分查找题目
目录 二维数组中的查找_牛客题霸_牛客网 (nowcoder.com) 寻找峰值_牛客题霸_牛客网 (nowcoder.com) 数组中的逆序对_牛客题霸_牛客网 (nowcoder.com) 旋转数组的最小数字_牛客题霸_牛客网 (nowcoder.com) 二维数组中的查找_牛客题霸_牛客网 (nowcoder.com) 题意:…...

【QT】自定义组件ui类添加到主ui界面方法
1.添加自定义组件到项目中 add new选择如下 写好类方法,确定即可 2.将新创建的ui类加入到主ui界面 选中新创建ui类的父类空块,右键选择提升为 选择并添加新创建的类...
FFmpeg 多图片合成视频带字幕和音乐+特效(淡入淡出,圆圈黑色淡出)
FFmpeg 多图片合成视频带字幕和音乐+特效(淡入淡出,圆圈黑色淡出) 效果图1. 报错及解决2. xfade、xfade_opeccl 特效切换3. ffmpeg命令行详解4. 源码4.1 auto.bash4.2 geneFade.py4.3 python moviepy合并视频及音频按照(视频长度截取对应的音频在合并)4.4 命令行记录参考这…...

上网Tips: Linux截取动态效果图工具_byzanz
链接1 链接2 安装: sudo apt-get install byzanz 查看指令 说明 byzanz-record --help日常操作 xwininfo点击 待录制窗口 左上角 byzanz-record -x 72 -y 64 -w 1848 -h 893 -d 10 --delay5 -c /home/xixi/myGIF/test.gif小工具 获取鼠标坐标 xdotool getm…...

下载盗版网站视频并将.ts视频文件合并
. 1.分析视频请求123 2.数据获取和拼接 1.分析视频请求 1 通过抓包观察我们发现视频是由.ts文件拼接成的每一个.ts文件代表一小段2 通过观察0.ts和1.ts的url我们发现他们只有最后一段不同我们网上找到url获取的包3 我们发现index.m3u8中储存着所有的.ts文件名在拼接上前面固定…...

ElasticSearch - 基于 拼音分词器 和 IK分词器 模拟实现“百度”搜索框自动补全功能
目录 一、自动补全 1.1、效果说明 1.2、安装拼音分词器 1.3、自定义分词器 1.3.1、为什么要自定义分词器 1.3.2、分词器的构成 1.3.3、自定义分词器 1.3.4、面临的问题和解决办法 问题 解决方案 1.4、completion suggester 查询 1.4.1、基本概念和语法 1.4.2、示例…...
【kubernetes】kubernetes中的调度
1 调度过程 调度的本来含义是指决定某个任务交给某人来做的过程,kubernetes中的调度是指决定Pod在哪个Node上运行。 k8s的调度分为2个过程: 预选:去掉不满足条件的节点优选:对剩下符合条件的节点按照一些策略进行排序ÿ…...
java读取csv文件或者java读取字符串,找出引号内容,采用正则表达式书写
将一个csv文件复制出来将后缀改变为txt,我们就得到了一个文件文件打开这个txt文件,可以看到每一个字段之间都是用英文逗号隔开 正常的内容形似 20,C4,Pm,tem,tion,21,A4,E,H,"1,2,3,NA,aaa,bbbb,cccc,ddd,N/A,aaa,bbbb,cccc,ddd,tttttt对于这种我们只需要进行…...
【寻找关键钥匙】python实现-附ChatGPT解析
1.题目 寻找关键钥匙 知识点字符串、编程基础、正则表达式、排序 时间限制:1s 空间限制: 256MB 限定语言:不限 题目描述: 小强正在参加《密室逃生》游戏,当前关卡要求找到符合给定 密码K(升序的不重复小写字母组成)的箱子,并给出箱子编号,箱子编号为1~N。 每个箱子中都有一个…...

基于 QT 实现一个 Ikun 专属桌面宠物
Step0、实现思路 想到的思路有两种: 1、使用 QT 的状态机模式,参考官网文档,这个模式的解耦最佳 2、使用原生 Wigets,将窗口设置为透明无框,循环播放桌面宠物的状态 本文采用第二种思路,实现一个极简版…...

新闻报道的未来:自动化新闻生成与爬虫技术
概述 自动化新闻生成是一种利用自然语言处理和机器学习技术,从结构化数据中提取信息并生成新闻文章的方法。它可以实现大规模、高效、多样的新闻内容生产。然而,要实现自动化新闻生成,首先需要获取可靠的数据源。这就需要使用爬虫技术&#…...

C++ 并发编程实战 第八章 设计并发代码 二
目录 8.3 设计数据结构以提升多线程程序的性能 8.3.1 针对复杂操作的数据划分 8.3.2 其他数据结构的访问模式 8.4 设计并发代码时要额外考虑的因素 8.4.1 并行算法代码中的异常安全 8.4.2 可扩展性和Amdahl定律 8.4.3 利用多线程隐藏等待行为 8.4.4 借并发特性改进响应…...

list(链表)
文章目录 功能迭代器的分类sort函数(排序)merage(归并)unique(去重)removesplice(转移) 功能 这里没有“[]"的实现;原因:实现较麻烦;这里使用迭代器来实…...

使用代理IP进行安全高效的竞争情报收集,为企业赢得竞争优势
在激烈的市场竞争中,知己知彼方能百战百胜。竞争对手的信息对于企业来说至关重要,它提供了洞察竞争环境和市场的窗口。在这个信息时代,代理IP是一种实用的工具,可以帮助企业收集竞争对手的产品信息和营销活动数据,为企…...
【数学知识】一些数学知识,以供学习
矩阵的特征值和特征向量 https://zhuanlan.zhihu.com/p/104980382 矩阵的逆 https://zhuanlan.zhihu.com/p/163748569 对数似然方程(log-likelihood equation),简称“似然方程”: https://baike.baidu.com/item/%E5%AF%B9%E6%95%B0%E4%BC%BC%E7%84%B6%E6%96%B9%E7…...
JKChangeCapture swift 版本的捕捉属性变化的工具
在OC的时代里,大家捕捉属性的变化通常是通过KVO机制来实现的,KVO把所有的属性变化都放在了一个方法进行相应处理,并不友好,之前基于KVO的机制实现了一套属性变化工具JKKVOHelper,这里不就在过多介绍这个了,在swift的时…...

RISC-V 指令
RISC-V指令都是32位长。 文章目录 R-Type指令格式:I-Type指令格式:S-Type指令格式:B-Type指令格式:U-Type指令格式:UJ-Type指令格式:J-Type指令格式:R4-Type指令格式:F-Type指令格式:vC-Type指令格式:CB-Type指令格式:CIW-Type指令格式:CL-Type指令格式:R-Type指…...

[NOIP2011 提高组] 选择客栈
[NOIP2011 提高组] 选择客栈 题目描述 丽江河边有 n n n 家很有特色的客栈,客栈按照其位置顺序从 1 1 1 到 n n n 编号。每家客栈都按照某一种色调进行装饰(总共 k k k 种,用整数 0 ∼ k − 1 0 \sim k-1 0∼k−1 表示)&am…...

桂院校园导航 静态项目 二次开发教程 1.2
Gitee代码仓库:桂院校园导航小程序 GitHub代码仓库:GLU-Campus-Guide 先 假装 大伙都成功安装了静态项目,并能在 微信开发者工具 和 手机 上正确运行。 接着就是 将项目 改成自己的学校。 代码里的注释我就不说明了,有提到 我…...
private static final long serialVersionUID = 1L的作用是什么?
1.作用是什么? 当一个类被序列化后,存储在文件或通过网络传输时,这些序列化数据会包含该类的结构信息。当反序列化操作发生时,Java虚拟机会根据序列化数据中的结构信息来还原对象。 但是,如果在序列化之后,…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...

React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...

USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...

无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...