「剑指Offer」Day30：分治算法（困难）
剑指 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. 数组中的逆序对
题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
思路
看到这道题最先想到的是暴力解法，但题目给出的限制是0 <= 数组长度 <= 50000，所以大概率会超时。
可以采用归并排序的分治思想，在合并两个排序数组的过程，每当遇到 左子数组当前元素 > 右子数组当前元素 时，意味着 「左子数组当前元素 至 末尾元素」 与 「右子数组当前元素」 构成了若干 「逆序对」 。
🔗参考题解：（LeetCode K神）https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/jian-zhi-offer-51-shu-zu-zhong-de-ni-xu-pvn2h/
代码实现
这里直接套用了归并排序的模板，只是修改了一下归并排序，在对左右两边进行有序合并的过程中，左边大于右边时就统计逆序对的数量
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];
}
}
}
查看11道真题和解析