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

    如果target>a[row][col],证明target在当前行的下方，我们往下边矩阵寻找；

    1. import java.util.*;
    2.  
    3.  
    4. public class Solution {
    5.     /**
    6.      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    7.      *
    8.      * 
    9.      * @param target int整型 
    10.      * @param array int整型二维数组 
    11.      * @return bool布尔型
    12.      */
    13.     public boolean Find (int target, int[][] array) {
    14.         // write code here
    15.         int n = array.length;
    16.         int m = array[0].length;
    17.         int row = 0;//行
    18.         int col = m-1;//列
    19.         while(row < n && col >= 0){
    20.             if(target == array[row][col]){
    21.                 return true;
    22.             }else if(target > array[row][col]){
    23.                 row++;
    24.             }else{
    25.                 col--;
    26.             }
    27.         }
    28.     
    29.         return false;
    30.     }
    31. }

    寻找峰值_牛客题霸_牛客网 (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.暴力枚举，只要比上一位大并且比下一位大，就是峰值，直接返回

    1. import java.util.*;
    2.  
    3.  
    4. public class Solution {
    5.     /**
    6.      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    7.      *
    8.      * 
    9.      * @param nums int整型一维数组 
    10.      * @return int整型
    11.      */
    12.     public int findPeakElement (int[] nums) {
    13.         // write code here
    14.         if(nums.length >= 2 && nums[0] > nums[1] || nums.length == 1){
    15.             return 0;
    16.         }
    17.         if(nums.length >= 2 && nums[nums.length-2] < nums[nums.length-1]){
    18.             return nums.length-1;
    19.         }
    20.         for(int i=1;i1;++i){
    21.             if(nums[i] > nums[i-1] && nums[i] > nums[i+1]){
    22.                 return i;
    23.             }
    24.         }
    25.         return -1;
    26.     }
    27. }

    解题思路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

    1. import java.util.*;
    2.  
    3.  
    4. public class Solution {
    5.     /**
    6.      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    7.      *
    8.      * 
    9.      * @param nums int整型一维数组 
    10.      * @return int整型
    11.      */
    12.     public int findPeakElement (int[] nums) {
    13.         // write code here
    14.        if(nums.length == 1){
    15.            return 0;
    16.        }
    17.        int left = 0;
    18.        int right = nums.length -1;
    19.        int mid;
    20.        while(left < right){
    21.             mid = (left + right) /2;
    22.             if(nums[mid] > nums[mid+1]){
    23.                 //mid比下一位大，有可能是山峰，往左遍历
    24.                 right = mid;//注意这里right是赋值mid，因为mid可能是山峰，所以要包含他去寻找
    25.             }else{
    26.                 //mid比它下一位小，mid+1有可能是山峰，向右走
    27.                 left = mid + 1;//从大的数开始往右查找
    28.             }
    29.        }
    30.         return right;
    31.     }
    32. }

    数组中的逆序对_牛客题霸_牛客网 (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)，运行超时 

    1. import java.util.*;
    2.  
    3.  
    4. public class Solution {
    5.     /**
    6.      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    7.      *
    8.      * 
    9.      * @param nums int整型一维数组 
    10.      * @return int整型
    11.      */
    12.     public int InversePairs (int[] nums) {
    13.         // write code here
    14.         int ans=0;
    15.         for(int i =0; i1; ++i){
    16.             for(int j=i; j< nums.length; ++j){
    17.                 if(nums[i] > nums[j]){
    18.                     ans++;
    19.                     ans %= 1000000007;
    20.                 } 
    21.             }
    22.         }
    23.         return ans;
    24.     }
    25. }

    解题思路2：

     基于归并排序法，在合并时候，如果右边的数小于左边的数，可以直接求出当前产生的逆序对的个数。

    1. import java.util.*;
    2.  
    3.  
    4. public class Solution {
    5.     int ans=0;
    6.     public int InversePairs (int[] nums) {
    7.         // write code here
    8.         if(nums.length < 2){
    9.             return 0;
    10.         }
    11.         mergeSort(nums,0,nums.length-1);
    12.         return ans;
    13.     }
    14.     public void mergeSort(int[] nums,int left,int right){
    15.         //分割点
    16.         int mid = (left+right)/2;
    17.         if(left < right){
    18.             mergeSort(nums,left,mid);
    19.             mergeSort(nums,mid+1,right);
    20.             //合并
    21.             merge(nums,left,mid,right);
    22.         }
    23.     }
    24.     public void merge(int[] nums,int left,int mid,int right){
    25.         //创建临时数组
    26.         int[] arr = new int[right - left + 1];
    27.         //临时数组下标起点
    28.         int c = 0;
    29.         int s = left;
    30.         int l = left;
    31.         int r = mid + 1;//左右数组的起始指针
    32.         while(l <= mid && r <= right){
    33.             //当左数组的元素小时，跳过
    34.             if(nums[l] <= nums[r]){
    35.                 //放入临时数组
    36.                 arr[c] = nums[l];
    37.                 c++;
    38.                 l++;
    39.             }else{
    40.                 //存在逆序对，统计
    41.                 arr[c] = nums[r];
    42.                 //逆序对个数，
    43.                 ans += mid+1 - l;
    44.                 ans %= 1000000007;
    45.                 c++;
    46.                 r++;
    47.             }
    48.         }
    49.         //左子数组还有元素，放入
    50.         while(l <= mid){
    51.             arr[c++] = nums[l++];
    52.         }
    53.         while(r <= right){
    54.             arr[c++] = nums[r++];
    55.         }
    56.         //临时数组放入数组原位置
    57.         for(int num: arr){
    58.             nums[s++] = num;
    59.         }
    60.     }
    61. }

    旋转数组的最小数字_牛客题霸_牛客网 (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]区间已经不符合非降序数组的要求了，所以这个区间旋转之后变成无序的，最小值在这里面寻找；

    如果是相等，则缩小范围继续寻找

    1. import java.util.*;
    2.  
    3.  
    4. public class Solution {
    5.     /**
    6.      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    7.      *
    8.      * 
    9.      * @param nums int整型一维数组 
    10.      * @return int整型
    11.      */
    12.     public int minNumberInRotateArray (int[] nums) {
    13.         // write code here
    14.         int left = 0;
    15.         int right = nums.length-1;
    16.         while(left < right){
    17.             int mid = (left + right) / 2;
    18.             if(nums[mid] > nums[right]){ //右子数组无序
    19.                 left = mid + 1;
    20.             }else if(nums[mid] < nums[right]){//左子数组无序
    21.                 right = mid;
    22.             }else{
    23.                 //如果是相等的话，缩小范围
    24.                 right--;
    25.             }
    26.         }
    27.         return nums[left];
    28.     }
    29. }

     

  • 相关阅读:
    集成测试规范
    使用树莓派学习Linux系统编程的 --- 库编程（面试重点）
    软件测试面试怎样介绍自己的测试项目？会问到什么程度？
    袋鼠云数栈前端从 Multirepo 到 Monorepo 研发效率提升探索之路
    计算机毕业设计选题推荐 -计算机专业毕业设计题目参考大全
    Python数据分析与机器学习38-Xgboost算法
    WordPress优化插件多站点管理软件
    linux设备模型：bus概念及pci_bus分析
    SQL优化--插入数据
    《嵌入式 – GD32开发实战指南》第19章 程序加密
  • 原文地址：https://blog.csdn.net/qq_37998848/article/details/133499885