数据范围：矩阵的长宽满足 0 \le n,m \le 5000≤n,m≤500 ， 矩阵中的值满足 0 \le val \le 10^90≤val≤109
进阶：空间复杂度 O(1)O(1) ，时间复杂度 O(n+m)O(n+m)

代码实现：

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;
        }
    }
}

旋转数组的最小数字

描述

算法思想二：二分法
解题思路：
排序数组的查找问题首先考虑使用 二分法 解决，其可将 遍历法 的 线性级别 时间复杂度降低至 对数级别

代码实现：

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];
    }
}

比较版本号

描述
牛客项目发布项目版本时会有版本号，比如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) {
        // write code here
       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) != '.'){
                num1 = num1 * 10 + (version1.charAt(i) - '0');
                i++;
            }
            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;