剑指 Offer 17. 打印从1到最大的n位数

题目描述

输入数字n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。 
输入: n = 1 输出: [1,2,3,4,5,6,7,8,9]
🔗题目链接：https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/

暴力解法

优化了直接从1遍历到最大的n位十进制数，通过确定首尾的方式一次遍历可确定前后两个位置的数 
class Solution {
    public int[] printNumbers(int n) {
        int length = 1;
        for(int i = 0; i < n; i++){
            length *= 10;
        }
        //求结果数组大小及最大的 n 位十进制数
        length = length - 1;
        int[] nums = new int[length];
        for(int i = 1; i <= (length + 1) / 2; i++){
            nums[i - 1] = i;
            nums[length - i] = length - i + 1;
        }
        return nums;
    }
}

剑指 Offer 51. 数组中的逆序对

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 
输入: [7,5,6,4] 输出: 5
🔗题目链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

思路

看到这道题最先想到的是暴力解法，但题目给出的限制是0 <= 数组长度 <= 50000，所以大概率会超时。
可以采用归并排序的分治思想，在合并两个排序数组的过程，每当遇到 左子数组当前元素 > 右子数组当前元素 时，意味着 「左子数组当前元素 至 末尾元素」 与 「右子数组当前元素」 构成了若干 「逆序对」 。

代码实现

这里直接套用了归并排序的模板，只是修改了一下归并排序，在对左右两边进行有序合并的过程中，左边大于右边时就统计逆序对的数量
class Solution {
    int[] tmp; //保存合并排序的结果
    int count; //统计逆序对的个数
    public int reversePairs(int[] nums) {
        tmp = new int[nums.length];
        count = 0;
        mergeSort(nums, 0, nums.length - 1);
        return count;
    }
    public void mergeSort(int[] nums, int l, int r){ //归并排序
        //递归分治
        if(l >= r){
            return;
        }
        int mid = (l + r) / 2;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid+1, r);
        //将左右两边进行有序合并
        int left = l;
        int right = mid + 1;
        int index = 0;
        while(left <= mid && right <= r){
            if(nums[left] <= nums[right]){
                tmp[index++] = nums[left++];
            }else{
                //左边大于右边就统计逆序对的个数
                count += (mid - left + 1);
                tmp[index++] = nums[right++];
            }
        }
        while(left <= mid){
            tmp[index++] = nums[left++];
        }
        while(right <= r){
            tmp[index++] = nums[right++];
        }
        //将该区间的排序结果重新赋给nums
        for (int k = 0; k < r - l + 1; k++) {
            nums[k + l] = tmp[k];
        }
    }
}