二分查找/排序

BM17 二分查找-I

public class Solution {
    public int search (int[] nums, int target) {
        if(nums.length == 0) return -1;
        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        // 没找到，返回-1
        return -1;
    }
}

BM18 二维数组中的查找

public class Solution {
    public boolean Find(int target, int [][] array) {
        int m = array.length, n = array[0].length;
        // 从左上角开始查找
        int row = 0, col = n - 1;
        while(row < m && col >= 0){
            // 找到，返回true
            if(array[row][col] == target) return true;
            else if(array[row][col] > target){
                col--;
            }else{
                row++;
            }
        }
        // 未找到，返回false
        return false;
    }
}

BM19 寻找峰值（注意）

public class Solution {
    public int findPeakElement (int[] nums) {
        /**
        峰值的特点：
        1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
        2.假设 nums[-1] = −∞, nums[n] = −∞
        3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
        要求时间复杂度为O(logN)
        */
        int left = 0, right = nums.length - 1;
        while(left < right){
            int mid = left + ((right - left) >> 1);
            // left和right均向山峰靠近
            if(nums[mid] > nums[mid + 1]) right = mid;
            else left = mid + 1;
        }
        return left;
    }
}

BM20 数组中的逆序对(归并排序)

public class Solution {
    // 逆序对即为数组排序过程中元素交换的次数
    // 暴力解法可采用冒泡排序算法
    // 这里采用归并排序算法
    
    int count = 0;// 统计交换次数
    public int InversePairs(int [] array) {
        // 归并排序
        sort(array, 0, array.length - 1);
        return count;
    }
    
    /************************归并排序算法*********************************/
    void sort(int[] nums, int left, int right) {
        if (left == right) {// 单一元素，有序，直接返回
            return;
        }
        int mid = left + (right - left) /2;// 取中点划分
        sort(nums, left, mid);// 左边数组排序
        sort(nums, mid + 1, right);// 右边数组排序

        /****** 后序位置 ******/
        // 合并两个排好序的数组
        merge(nums, left, mid, right);
    }

    // 合并两个排好序的子数组
    public void merge(int[] nums, int left, int mid, int right) {
        // 创建一个空辅助数组
        int[] temp = new int[nums.length];
        // 将nums中的数据移到temp中，nums用于存放排序结果
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }
        // 数组双指针技巧，合并两个有序数组
        int i = left, j = mid + 1;
        for (int p = left; p <= right; p++) {// 通过遍历，将结果存储至nums
            if (i == mid + 1) {// 左半边数组已全部被合并
                nums[p] = temp[j++];// 将右半边剩余内容复制到nums中
            } else if (j == right + 1) {// 右半边数组已全部被合并
                nums[p] = temp[i++];// 将左半边内容复制到nums中
            } else if (temp[i] > temp[j]) {// 左边元素大于右边元素
                
                /***************此时存在逆序对,需进行操作**************************/
                count += (mid + 1 - i);
                count %= 1000000007;
                /***************************************************************/
                nums[p] = temp[j++];
            } else {// 右边元素大于等于左边元素
                nums[p] = temp[i++];
            }
        }
    }
}

BM21 寻找数组中的最小数字(注意)

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length == 0) return -1;
        int left = 0, right = array.length - 1;
        while(left < right){
            // 有序，则left处的元素最小
            if(array[left] < array[right]) return array[left];
            // 无序，二分查找
            int mid = left + (right - left) / 2;
            if(array[mid] > array[right]) left = mid + 1;
            else if(array[mid] < array[right]) right = mid;
            else right--;
        }
        return array[left];
    }
}

BM22 比较版本号

import java.util.*;
public class Solution {
    public int compare (String version1, String version2) {
        // 将版本号划分为修订号字符串
        String[] ver1 = version1.split("\\.");
        String[] ver2 = version2.split("\\.");
        // 获取转换成数字数字的长度
        int len = Math.max(ver1.length, ver2.length);
        int[] verNum1 = new int[len];
        int[] verNum2 = new int[len];
        // 将修订号转换成数字，并存储在数组中
        for(int i = 0; i < len; i++){
            // 转换成数字，自动忽略前导0
            verNum1[i] = i < ver1.length ? stringToNumber(ver1[i]) : 0;
            verNum2[i] = i < ver2.length ? stringToNumber(ver2[i]) : 0;
            // 比较两个修订号
            if(verNum1[i] > verNum2[i]) return 1;
            if(verNum1[i] < verNum2[i]) return -1;
        }
        return 0;
    }
    
    // 将字符串转化为数字
    public int stringToNumber(String str){
        char[] chars = str.toCharArray();
        int number = 0;
        for(int i = 0; i < chars.length; i++){
            number = number * 10 + (chars[i] - '0');
        }
        return number;
    }
}