【牛客网-面试必刷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];}
}