当前位置: 首页 > news >正文

【牛客网-面试必刷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) 题意&#xff1a…...

【QT】自定义组件ui类添加到主ui界面方法

1.添加自定义组件到项目中 add new选择如下 写好类方法&#xff0c;确定即可 2.将新创建的ui类加入到主ui界面 选中新创建ui类的父类空块&#xff0c;右键选择提升为 选择并添加新创建的类...

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 安装&#xff1a; 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 调度过程 调度的本来含义是指决定某个任务交给某人来做的过程&#xff0c;kubernetes中的调度是指决定Pod在哪个Node上运行。 k8s的调度分为2个过程&#xff1a; 预选&#xff1a;去掉不满足条件的节点优选&#xff1a;对剩下符合条件的节点按照一些策略进行排序&#xff…...

java读取csv文件或者java读取字符串,找出引号内容,采用正则表达式书写

将一个csv文件复制出来将后缀改变为txt,我们就得到了一个文件文件打开这个txt文件&#xff0c;可以看到每一个字段之间都是用英文逗号隔开 正常的内容形似 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、实现思路 想到的思路有两种&#xff1a; 1、使用 QT 的状态机模式&#xff0c;参考官网文档&#xff0c;这个模式的解耦最佳 2、使用原生 Wigets&#xff0c;将窗口设置为透明无框&#xff0c;循环播放桌面宠物的状态 本文采用第二种思路&#xff0c;实现一个极简版…...

新闻报道的未来:自动化新闻生成与爬虫技术

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

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函数&#xff08;排序&#xff09;merage&#xff08;归并&#xff09;unique(去重&#xff09;removesplice&#xff08;转移&#xff09; 功能 这里没有“[]"的实现&#xff1b;原因&#xff1a;实现较麻烦&#xff1b;这里使用迭代器来实…...

使用代理IP进行安全高效的竞争情报收集,为企业赢得竞争优势

在激烈的市场竞争中&#xff0c;知己知彼方能百战百胜。竞争对手的信息对于企业来说至关重要&#xff0c;它提供了洞察竞争环境和市场的窗口。在这个信息时代&#xff0c;代理IP是一种实用的工具&#xff0c;可以帮助企业收集竞争对手的产品信息和营销活动数据&#xff0c;为企…...

【数学知识】一些数学知识,以供学习

矩阵的特征值和特征向量 https://zhuanlan.zhihu.com/p/104980382 矩阵的逆 https://zhuanlan.zhihu.com/p/163748569 对数似然方程(log-likelihood equation)&#xff0c;简称“似然方程”: https://baike.baidu.com/item/%E5%AF%B9%E6%95%B0%E4%BC%BC%E7%84%B6%E6%96%B9%E7…...

JKChangeCapture swift 版本的捕捉属性变化的工具

在OC的时代里&#xff0c;大家捕捉属性的变化通常是通过KVO机制来实现的&#xff0c;KVO把所有的属性变化都放在了一个方法进行相应处理&#xff0c;并不友好&#xff0c;之前基于KVO的机制实现了一套属性变化工具JKKVOHelper,这里不就在过多介绍这个了&#xff0c;在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 家很有特色的客栈&#xff0c;客栈按照其位置顺序从 1 1 1 到 n n n 编号。每家客栈都按照某一种色调进行装饰&#xff08;总共 k k k 种&#xff0c;用整数 0 ∼ k − 1 0 \sim k-1 0∼k−1 表示&#xff09;&am…...

桂院校园导航 静态项目 二次开发教程 1.2

Gitee代码仓库&#xff1a;桂院校园导航小程序 GitHub代码仓库&#xff1a;GLU-Campus-Guide 先 假装 大伙都成功安装了静态项目&#xff0c;并能在 微信开发者工具 和 手机 上正确运行。 接着就是 将项目 改成自己的学校。 代码里的注释我就不说明了&#xff0c;有提到 我…...

private static final long serialVersionUID = 1L的作用是什么?

1.作用是什么&#xff1f; 当一个类被序列化后&#xff0c;存储在文件或通过网络传输时&#xff0c;这些序列化数据会包含该类的结构信息。当反序列化操作发生时&#xff0c;Java虚拟机会根据序列化数据中的结构信息来还原对象。 但是&#xff0c;如果在序列化之后&#xff0c…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

【Android】Android 开发 ADB 常用指令

查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...