题目根据视频整理, 结合视频理解效果更佳
题目有两道, 不过是完全相同的
思路
题目 65 — 数组中的逆序对
没有给出数据范围, 直接解题
代码
class Solution {
// 程序入口
public int inversePairs(int[] nums) {
// 进行查找
return mergeSort(nums, 0, nums.length - 1);
}
// 语义: 对 nums的范围 [l...r]内的数据进行计算逆序对, 并且对 [l...r]中的数据进行排序
private int mergeSort(int[] nums, int l, int r) {
// 递归结束, 只有一个数字时, 逆序对为 0
if (l >= r) return 0;
int res = 0;
int[] tmp = new int[r - l + 1];
int mid = l + r >> 1;
// 情况一和情况二, 并对左右数组进行排序
res += mergeSort(nums, l, mid) + mergeSort(nums, mid + 1, r);
// 进行归并
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (nums[i] <= nums[j])
tmp[k++] = nums[i++];
else {
tmp[k++] = nums[j++];
// 情况三
res += mid - i + 1;
}
}
// 扫尾
while (i <= mid) tmp[k++] = nums[i++];
while (j <= r) tmp[k++] = nums[j++];
// tmp -> nums
for (i = l, j = 0; i <= r; i++, j++) {
nums[i] = tmp[j];
}
return res;
}
}
题目 788 — 逆序对的数量
注意: 给出数据范围 1~ 10^5
所以最多包含逆序对数量为 2^10, 不能使用 int, 使用 long, 读入数据使用 BufferReader
代码
import java.io.*;
public class Main {
static int N = 100010; // 数据规模为 10w
static int[] arr = new int[N];
public static void main(String[] args) throws IOException {
// 输入数据进行初始化
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine());
String[] arrStr = reader.readLine().split(" ");
for (int i = 0; i < n; i++)
arr[i] = Integer.parseInt(arrStr[i]);
// 打印结果
System.out.println(mergeSort(0, n - 1));
// 关闭输入流
reader.close();
}
// 语义: 对 [l, r]进行排序, 并计算 [l,r]中逆序对的数量
private static long mergeSort(int l, int r) {
// 递归结束, 只有一个元素, 逆序对为 0
if (l >= r) return 0;
int mid = l + r >> 1;
long res = 0;
// 情况一和情况二, 并对左右数组进行排序
res += mergeSort(l, mid) + mergeSort(mid + 1, r);
// 归并排序
int[] tmp = new int[r - l + 1];
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
else {
tmp[k++] = arr[j++];
// 情况三
res += mid - i + 1;
}
}
// 扫尾
while (i <= mid) tmp[k++] = arr[i++];
while (j <= r) tmp[k++] = arr[j++];
// tmp -> arr
for (i = l, j = 0; i <= r; i++, j++) {
arr[i] = tmp[j];
}
return res;
}
}
不会超时吗
请问为什么是res+=mid-i+1呢
我觉得应该是这个比他大,右边的应该都比他大了,直接减
很优秀,不过有个疑问也是做题的时候遇到的,如果我们输入数组的时候用的是逗号隔开报错这个怎么避免
String[] arrStr = reader.readLine().split(“,”);
要申请10010个元素的静态数组,不浪费空间吗?不应该按照的输入的数个数来申请数组,更合理吧
按个数的话会在递归里不断的申请空间,这样可能会超出时间吧
请问读入数据一定要BufferedReader吗
BufferedReader在读入大数的时候速度更快,就是类似scanf的读入速度比cin快一样