算法练习（1）：牛客在线编程02 二分法

柔情只为你懂 2023-10-13 22:09 39阅读 0赞

package jz.bm;
    
    public class bm2 {
        
        /**
         * BM17 二分查找-I
         * 请实现无重复数字的升序数组的二分查找
         * 给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，
         * 写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1
         */
        public int search (int[] nums, int target) {
        
            int left = 0, right = nums.length - 1;
            while (left <= right) {
         //left可以等于right,只有一个数字的情况
                int mid = (left + right) / 2;
                if (target == nums[mid]) {
        
                    return mid;
                } else if (target > nums[mid]) {
        
                    left = mid + 1;
                } else {
        
                    right = mid - 1;
                }
            }
            return -1;
        }
    
        /**
         * BM18 二维数组中的查找
         * 在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
         * 每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
         */
        public boolean Find(int target, int [][] array) {
        
            int row = array.length;
            if (row == 0) {
        
                return false;
            }
            int col = array[0].length;
            int i = row - 1;
            int j = 0; //从左下角开始二分
            while (i >= 0 && j <col) {
        
                if (target == array[i][j]) {
        
                    return true;
                } else if (target > array[i][j]) {
        
                    j++;
                } else {
        
                    i--;
                }
            }
            return false;
        }
    
        /**
         * BM19 寻找峰值
         * 给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
         * 1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
         * 2.假设 nums[-1] = nums[n] =
         * 3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
         * 4.你可以使用O(logN)的时间复杂度实现此问题吗？
         */
        public int findPeakElement (int[] nums) {
        
            int left = 0, right = nums.length - 1;
            while (left < right) {
         //收缩区间，直到收缩到只有一个值
                int mid = (left + right) / 2;
                if (nums[mid] < nums[mid + 1]) {
         //峰值在右
                    left = mid + 1;
                } else {
         //峰值左
                    right = mid;
                }
            }
            return left;
        }
    
        /**
         * BM20 数组中的逆序对
         * 在数组中的两个数字，如果前面一个数字大于后面的数字，
         * 则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
         */
        public int InversePairs(int [] array) {
        
            int[] temp = new int[array.length];
            return sort2(array, 0, array.length - 1, temp);
        }
        private int sort2(int[] array, int start, int end, int[] temp) {
        
            if (start >= end) {
        
                return 0;
            }
            int mid = (start + end) / 2;
            int res = sort2(array, start, mid, temp) + sort2(array, mid + 1, end, temp);
            res = res % 1000000007;
            for (int i = start; i <= end; i++) {
        
                temp[i] = array[i];
            }
            int i = start;
            int j = mid + 1;
            int index = start;
            while (i <= mid || j <= end) {
        
                if (i == mid + 1) {
        
                    array[index] = temp[j++];
                } else if (j == end + 1) {
        
                    array[index] = temp[i++];
                } else if (temp[i] <= temp[j]) {
        
                    array[index] = temp[i++];
                } else {
        
                    array[index] = temp[j++];
                    res += mid - i + 1;
                }
                index++;
            }
            res = res % 1000000007;
            return res;
        }
    
        /**
         * BM21 旋转数组的最小数字
         * 有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，
         * 将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，
         * 比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。
         */
        public int minNumberInRotateArray(int [] array) {
        
            int left = 0, right = array.length - 1;
            while (left < right) {
        
                int mid = (left + right) / 2;
                if (array[mid] < array[right]) {
        
                    right = mid; //右边是上升趋势，则最小值在左
                } else if (array[mid] > array[right]) {
        
                    left = mid + 1; //右边是下降趋势，最小值只能在右区，且肯定不是mid点
                } else {
        
                    right--; //减去重复，缩小区域
                }
            }
            return array[left]; //最终left == right
        }
    
        /**
         * BM22 比较版本号
         * 牛客项目发布项目版本时会有版本号，比如1.02.11，2.14.4等等
         * 现在给你2个版本号version1和version2，请你比较他们的大小
         * 版本号是由修订号组成，修订号与修订号之间由一个"."连接。1个修订号可能有多位数字组成，
         * 修订号可能包含前导0，且是合法的。例如，1.02.11，0.1，0.2都是合法的版本号
         * 每个版本号至少包含1个修订号。
         * 修订号从左到右编号，下标从0开始，最左边的修订号下标为0，下一个修订号下标为1，以此类推。
         */
        public int compare (String version1, String version2) {
        
            String[] str1 = version1.split("\\.");
            String[] str2 = version2.split("\\.");
            int len = Math.max(str1.length, str2.length);
            for (int i = 0; i < len; i++) {
        
                String s1 = i >= str1.length ? "0" : str1[i];
                String s2 = i >= str2.length ? "0" : str2[i];
                int a1 = Integer.parseInt(s1);
                int a2 = Integer.parseInt(s2);
                if (a1 > a2) {
        
                    return 1;
                } else if (a1 < a2) {
        
                    return -1;
                }
            }
            return 0;
        }
    }