本文主要是介绍【牛客网-面试必刷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】二分查找题目的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!