牛客刷题：二分查找排序（JAVA版）

淩亂°似流年 2023-09-26 11:51 65阅读 0赞

## 牛客刷题：二分查找/排序（JAVA版） ##

## 每一步代码，都有我的注释，我感觉应该挺详细了，不懂可以私聊我，我都会讲解的 ##

## BM17 二分查找 ##

![在这里插入图片描述][093942840ea14128b30d90c7e2d58f52.png]

### 我的：我下面说的指针代指下标，之前写的太多了，懒得动了，看得懂就行 ###

> 二分查找指的就是，在有序数组中，先从中间找，中间的值小了，就重新从右边找（有序：从大到小），中间的值大了，就在左边找（有序：从小到大），一直重复此操作，直到找到，或者没找到（左指针比右指针大），返回值

import java.util.*;
    public class Solution {
        
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         *
         * @param nums int整型一维数组
         * @param target int整型
         * @return int整型
         */
        public int search (int[] nums, int target) {
        
            //定义左右指针，左指针指向头就是0，右指针指向结尾
            int left = 0, right = nums.length;
            //如果左指针比右指针大，就说明到头都没有找到这个值，所以就退出了
            while (right > left) {
        
                //每次都找中间的值
                int x = (left + right) / 2;
                //target比中间的值大就说明，肯定值肯定要去右边找
                if (target > nums[x]) {
        
                    //左指针要比中间那个大一个
                    left = x+1;
                //target比中间的值小就说明，肯定值肯定要去做边找
                } else if (target < nums[x]) {
        
                    //左指针指向中间那个值
                    right = x;
                //等于的话就输出
                } else if (target == nums[x]) {
        
                    return x;
                } else {
        
                    //没有就输出-1
                    return -1;
                }
            }
            //没有就输出-1
            return -1;
        }
    }

### 题解： ###

import java.util.*;
    public class Solution {
        
        public int search (int[] nums, int target) {
        
            int l = 0;
            int r = nums.length - 1;
            //从数组首尾开始，直到二者相遇
            while(l <= r){
         
                //每次检查中点的值
                int m = (l + r) / 2; 
                if(nums[m] == target)
                    return m;
                //进入左的区间
                if(nums[m] > target) 
                    r = m - 1;
                //进入右区间
                else 
                    l = m + 1;
            }
            //未找到
            return -1; 
        }
    }

## BM18 **二维数组中的查找** ##

![在这里插入图片描述][639aff9d6fd34a8aba9c9dffea75ab0a.png]

### 我的：暴力for循环 时间复杂度 O(n2)（太简单就不讲了） ###

public class Solution {
        
        public boolean Find(int target, int [][] array) {
        
            for (int[] ints : array) {
        
                for (int anInt : ints) {
        
                    if (target == anInt) return true;
                }
            }
            return false;
        }
    }

### 题解：因为题目所示，数字从左到右，从上至下依次递增，所以这里用的方法就是从大的到小的找 ###

![在这里插入图片描述][08e641c9a05d4cd1b04418d7db285d2e.png]

public class Solution {
        
        public boolean Find(int target, int [][] array) {
        
            //下面这两个if是判断有无值，没值就不需要浪费时间循环了，直接输出
            int rows = array.length;
            if(rows == 0){
        
                return false;
            }
            int cols = array[0].length;
            if(cols == 0){
        
                return false;
            }
            // 左下 ， rows指的 int[] 里面的长度，row 是指 最后一个值的下标，意思就是从后往前遍历
            int row = rows-1;
            int col = 0;
            //row<0 了的话，就说明到头了，col<cols的意思：题目所示《每个一维数组的长度相同》，所以只要col大于cols的话，就找不到值了，会报错
            while(row>=0 && col<cols){
        
                //从最后一组数找（最大）如果第一个小于值，那么所有数组中的第一个值都比target要小（题示：从上至下依次递增），只需要加大col就行
                if(array[row][col] < target){
        
                    col++;
                //如果target比第一个小，那么这最后一组直接淘汰，因为后面的值都比第一个大（题示：从左到右依次递增），只需要找前面的数组就行
                }else if(array[row][col] > target){
        
                    row--;
                //这里是指 array[row][col] == target
                }else{
        
                    return true;
                }
            }
            // 没找到就返回false
            return false;
        }
    }

![在这里插入图片描述][a49878424ed74184bb8b674c08d05035.png]

## **BM19** **寻找峰值** ##

![在这里插入图片描述][3a8bd681ffa04acb97c9970e4a0064c6.png]

### 我的：这个题有五个情况， ###

### 1、就是说如果数只有一个的时候，那么就是就返回0； ###

### 2、就是说如果数只有两个的时候，如：\{5,8\} 那么下标也就是返回值应该为8的下标就是1 ###

### 3、第一个比第二个大，返回0就行 ###

### 4、到最后的时候还没出结果，说明最后一个就是最大的值，如：\{1,2,3,4,5\} 那么返回值应该是5的下标就是4 ###

### 5、峰值在中间，左右边都比自己小 ###

import java.util.*;
    
    
    public class Solution {
        
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         *
         * @param nums int整型一维数组
         * @return int整型
         */
        public int findPeakElement (int[] nums) {
        
            // 把第一个值取出来，作为左边的值，这个值会一直与下面的nums[i]做比较
            int left = nums[0];
            // 这是第一种情况
            if (nums.length == 1) return 0;
            // 这是第二种情况
            if (nums.length == 2) {
        
                if (nums[1] < left) {
        
                    return 0;
                } else return 1;
            }
            //从下标1开始遍历每一个值
            for (int i = 1; i < nums.length; i++) {
        
                // 这是第三种情况
                if (nums[i] < left) {
        
                    return 0;
                }
                //i要比nums.length小一个，不然i + 1就会超出数组的长度
                // 这里我提个醒：nums.length是指数组nums的长度，是取不到的值，要比nums的最后一个下标大一，因为下标是从0开始递增的，如果这个都不清楚的同学，现在暂时不要管算法这块，去复习或者学习一个JavaSE的内容，把基础打牢一点
                if (i < nums.length - 1) {
        
                    //这是第五种情况
                    //如果这个if判断正确，就说明是峰值，返回下标
                    if (nums[i] > left && nums[i] > nums[i + 1]) return i;
                 //这是第四种情况
                //没找到的话，说明最后一个值最大，返回最后的下标就行 这里的 i ，是指nums.length - 1 ，因为上面if判断有误的话，就说明 i++ 了，那么i就要等于nums.length - 1
                } else return i;
            }
            //这里根本就没啥用，就是如果数组就不存在为空的时候返回这个而已
            return -1;
        }
    }

### 题解： ###

![在这里插入图片描述][8caeb2d2c6534e4d85d4c596b1137e51.png]

#### 图示： ####

![在这里插入图片描述][372011f877ce48d4b00e1eb2ecd56942.gif_pic_center]

import java.util.*;
    public class Solution {
        
        public int findPeakElement (int[] nums) {
        
            int left = 0;
            int right = nums.length - 1;
            //二分法
            while(left < right){
         
                int mid = (left + right) / 2;
                //右边是往下，不一定有坡峰
                if(nums[mid] > nums[mid + 1])
                    right = mid;
                //右边是往上，一定能找到波峰
                else
                    left = mid + 1;
            }
            //其中一个波峰
            return right; 
        }
    }

![在这里插入图片描述][ccae8794597d4fd081448f93fd4e6d74.png]

## **BM20** **数组中的逆序对** ##

![在这里插入图片描述][6e56e9354175413591f77dd367a7388b.png]

### 我的：暴力双层for循环（失败）时间复杂度：O(N^2)、空间复杂度：O(1) （超时：失败） ###

public class Solution {
        
        public int InversePairs(int [] array) {
        
            Integer nums = 0;
            for (int i = 0; i < array.length; i++) {
        
                for (int j = i + 1; j < array.length; j++) {
        
                    if (array[i] > array[j]) nums++;
                }
            }
            return nums;
        }
    }

![在这里插入图片描述][0f5fdc6d88974b368a4608b643e1ee77.png]

### 题解： ###

![在这里插入图片描述][8f021f14b164465f89c863e890130660.png]

public class Solution {
        
        int count = 0;
        public int InversePairs(int [] array) {
        
            // 长度小于2则无逆序对
            if(array.length < 2)
                return 0;
            // 进入归并
            mergeSort(array,0,array.length-1);
            return count;
        }
    
        public void mergeSort(int[] array,int left,int right){
        
            // 找分割点
            int mid = left+(right-left)/2;
            if(left < right){
        
                // 左子数组
                mergeSort(array,left,mid);
                // 右子数组
                mergeSort(array,mid+1,right);
                // 并
                merge(array,left,mid,right);
            }
        }
    
        public void merge(int[] array,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(array[l] <= array[r]){
        
                    // 放入临时数组
                    arr[c] = array[l];
                    // 临时数组下标+1
                    c++;
                    // 左子数组指针右移
                    l++;
                }else{
         // 否则，此时存在逆序对
                    // 放入临时数组
                    arr[c] = array[r];
                    // 逆序对的个数为    左子数组的终点- 当前左子数组的当前指针
                    count += mid+1-l;
                    count %= 1000000007;
                    // 临时数组+1
                    c++;
                    // 右子数组的指针右移
                    r++;
                }
            }
    
            // 左子数组还有元素时，全部放入临时数组
            while(l <= mid)
                arr[c++] = array[l++];
            // 右子数组还有元素时，全部放入临时数组
            while(r <= right)
                arr[c++] = array[r++];
            // 将临时数组中的元素放入到原数组的指定位置
            for(int num:arr){
        
                array[s++] = num;
            }
        }
    }

## **BM21** **旋转数组的最小数字** ##

![在这里插入图片描述][de1f5ea9d1a24590aa80445957d90364.png]

### 我的：还是暴力法 这个时间复杂度O(N)，通不过案例（失败） ###

import java.util.*;
    public class Solution {
        
        public int minNumberInRotateArray(int [] array) {
        
            //数组一定有元素
            int res = array[0]; 
            //遍历数组
            for(int i = 1; i < array.length; i++) 
                //每次维护最小值
                res = Math.min(res, array[i]); 
            return res;
        }
    }

### 题解： ###

![在这里插入图片描述][faa0b7ef2d854f488cae8229d68aa0ff.png]

import java.util.ArrayList;
    public class Solution {
        
        public int minNumberInRotateArray(int [] array) {
        
            // 特殊情况判断
            if (array.length== 0) {
        
                return 0;
            }
            // 左右指针i j
            int i = 0, j = array.length - 1;
            // 循环
            while (i < j) {
        
                // 找到数组的中点 m
                int m = (i + j) / 2;
                // m在左排序数组中，旋转点在 [m+1, j] 中
                if (array[m] > array[j]) i = m + 1;
                // m 在右排序数组中，旋转点在 [i, m]中
                else if (array[m] < array[j]) j = m;
                // 缩小范围继续判断
                else j--;
            }
            // 返回旋转点
            return array[i];
        }
    }

## **BM22** **比较版本号**：这里讲解一下示例二是怎么回事，“1.1”,“1.01”，这两个比较可以看成 1与1 比较，然后 1与01 比较，所以是相同的 ##

![在这里插入图片描述][3d135cac4f834e429323b4a82254ad05.png]

### 我的：这道题与我在百度笔试中遇见的题目类似，可惜当时没做来，做的很复杂，使用BigInteger来装 （>\_<） ，所以在这就不嫌丑了，直接来题解。 ###

//好吧，我告诉大家我当时的思路，就是获取全部的数字，第一个`.`之前的数字为整数，其他变成小数，比较他们的大小，（如1.0.1就变成了1.01），但当数字特别大的时候，long就装不下了(long只能到19位数字)，要用StringBuild来装，再用BigInteger转成数字进行比较，遍历的多了就特别的慢，而且截取不了1.01中的0，1.01与1.1比较的时候，就会出现（小数比较）1.1>1.01的情况
    //但是按照题目要求，1.1与1.01比较的时候，是从 `.` 拆开来比较，就是1与1比较，1与01比较，所以是相等的，我就做错了

### 题解：我简要的说明一下思路，每次都截取 `.` 之前的数字进行比较，如果相等的话，就跳过 `.` 这个节点，再截取下一个 `.` 之前的数字进行比较，直到最后都没分出大小的话，就说明相等，返回0 ###

![在这里插入图片描述][aa6b2e4a05ce49489888096885b3b6c9.png]

#### 图解： ####

![在这里插入图片描述][b8fa326d21804a408fedd93877991e3c.gif_pic_center]

import java.util.*;
    public class Solution {
        
        public int compare (String version1, String version2) {
        
            int n1 = version1.length();
            int n2 = version2.length();
            int i = 0, j = 0;
            //直到某个字符串结束
            while(i < n1 || j < n2){
        
                // 截取 . 之前的数字 用来进行比较
                long num1 = 0;
                //从下一个点前截取数字
                while(i < n1 && version1.charAt(i) != '.'){
         
                    //这里的version1.charAt(i) - '0' 是因为 version1.charAt(i) 是 char类型 如果要与 int 类型相加的话 ， 会转换成 ascii码 值 ，所以需要减 '0' 得到数字；
                    //例如：'1'的ascii码为49，'0'的ascii码为48，用 1 + version1.charAt(i) 得到的会是 50（49+1） ；如果1 + (version1.charAt(i) - '0')得到的数字就为 2（1+（49-48））；
                    num1 = num1 * 10 + (version1.charAt(i) - '0');
                    i++;
                }
                //跳过点 比如：version1="1.20.2" 上一步while循环 就把字符串 version1 变成 .20.2 要跳过 . 执行下一个循环 （也不是变成，是截取，如果i不自增1，下一个循环就会从 . 开始，会造成while不会执行，这里为了好讲解，使用变成这个错的解释，但各位大佬看得懂就行）
                i++; 
                
                // 这里就跟上面一样了
                long num2 = 0;
                //从下一个点前截取数字
                while(j < n2 && version2.charAt(j) != '.'){
         
                    num2 = num2 * 10 + (version2.charAt(j) - '0');
                    j++;
                }
                //跳过点 同上
                j++; 
                
                //比较数字大小 每次遍历完 . 之前的数字就进行比较
                if(num1 > num2) 
                    return 1;
                if(num1 < num2)
                    return -1;
            }
            //版本号相同
            return 0; 
        }
    }

## 感谢牛客网的题目与题解，如果侵权联系删除 ##

[093942840ea14128b30d90c7e2d58f52.png]: https://img-blog.csdnimg.cn/093942840ea14128b30d90c7e2d58f52.png
[639aff9d6fd34a8aba9c9dffea75ab0a.png]: https://img-blog.csdnimg.cn/639aff9d6fd34a8aba9c9dffea75ab0a.png
[08e641c9a05d4cd1b04418d7db285d2e.png]: https://img-blog.csdnimg.cn/08e641c9a05d4cd1b04418d7db285d2e.png
[a49878424ed74184bb8b674c08d05035.png]: https://img-blog.csdnimg.cn/a49878424ed74184bb8b674c08d05035.png
[3a8bd681ffa04acb97c9970e4a0064c6.png]: https://img-blog.csdnimg.cn/3a8bd681ffa04acb97c9970e4a0064c6.png
[8caeb2d2c6534e4d85d4c596b1137e51.png]: https://img-blog.csdnimg.cn/8caeb2d2c6534e4d85d4c596b1137e51.png
[372011f877ce48d4b00e1eb2ecd56942.gif_pic_center]: https://img-blog.csdnimg.cn/372011f877ce48d4b00e1eb2ecd56942.gif#pic_center
[ccae8794597d4fd081448f93fd4e6d74.png]: https://img-blog.csdnimg.cn/ccae8794597d4fd081448f93fd4e6d74.png
[6e56e9354175413591f77dd367a7388b.png]: https://img-blog.csdnimg.cn/6e56e9354175413591f77dd367a7388b.png
[0f5fdc6d88974b368a4608b643e1ee77.png]: https://img-blog.csdnimg.cn/0f5fdc6d88974b368a4608b643e1ee77.png
[8f021f14b164465f89c863e890130660.png]: https://img-blog.csdnimg.cn/8f021f14b164465f89c863e890130660.png
[de1f5ea9d1a24590aa80445957d90364.png]: https://img-blog.csdnimg.cn/de1f5ea9d1a24590aa80445957d90364.png
[faa0b7ef2d854f488cae8229d68aa0ff.png]: https://img-blog.csdnimg.cn/faa0b7ef2d854f488cae8229d68aa0ff.png
[3d135cac4f834e429323b4a82254ad05.png]: https://img-blog.csdnimg.cn/3d135cac4f834e429323b4a82254ad05.png
[aa6b2e4a05ce49489888096885b3b6c9.png]: https://img-blog.csdnimg.cn/aa6b2e4a05ce49489888096885b3b6c9.png
[b8fa326d21804a408fedd93877991e3c.gif_pic_center]: https://img-blog.csdnimg.cn/b8fa326d21804a408fedd93877991e3c.gif#pic_center