归并排序与逆序对问题
归并排序
private void sort(int[] nums) {
int[] temp = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
temp[i] = nums[i];
}
sort(nums, temp, 0, nums.length-1);
}
private void sort(int[] nums, int[] temp, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
sort(nums, temp, left, mid);
sort(nums, temp, mid + 1, right);
merge(nums, temp, left, mid, right);
}
// 合并两个有序数组，左数组的下标[left, mid]，右数组的下标[mid+1, right]
private void merge(int[] nums, int[] temp, int left, int mid, int right) {
// temp数组保存nums合并前从left到right的值，即保存左、右两个子数组，用作赋值和值比较
for (int i = left; i<= right; i++) {
temp[i] = nums[i];
}
// i,j分别是左右两个有序的子数组待插入nums的下标
int i = left;
int j = mid+1;
for (int k = left; k <= right; k++) {
if (i > mid) {
// 左子数组已经全部插入nums，剩下的只有右子数组
nums[k] = temp[j++];
} else if (j > right) {
// 右子数组已经全部插入nums，剩下的只有左子数组
nums[k] = temp[i++];
} else if (temp[i] < temp[j]) {
// 左边的值更小，插入左边的i
nums[k] = temp[i++];
} else if (temp[i] == temp[j]){
// 左右的值相等，插入i和j均可，这里插入i
nums[k] = temp[i++];
} else {
// 右边的值更小，插入右边的j
nums[k] = temp[j++];
}
}
}
复制代码逆序对问题
leetcode:剑指 Offer 51. 数组中的逆序对 - 力扣（LeetCode） (leetcode-cn.com)
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
输入: [7,5,6,4]
输出: 5
复制代码有两种解法：
解法1考虑的是，j插入时，根据左数组比j大的值来更新逆序对。
解法2考虑的是，i插入时，根据右数组比i小的值来更新逆序对。
解法1: 注意到在归并排序合并的阶段，如果temp[i] > temp[j] ，则出现了逆序对，此时从[i,mid]的所有元素，都比右数组中剩下的元素要大，逆序对的数量可以增加mid-i+1个。如果右子数组已经全部合并，即temp[j]不存在，逆序对的数量+0。
对上述归并排序的代码稍作修改：
int ans = 0; // 逆序对的个数
private int reversePairs(int[] nums) {
int[] temp = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
temp[i] = nums[i];
}
sort(nums, temp, 0, nums.length-1);
return ans;
}
private void sort(int[] nums, int[] temp, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
sort(nums, temp, left, mid);
sort(nums, temp, mid + 1, right);
merge(nums, temp, left, mid, right);
}
private void merge(int[] nums, int[] temp, int left, int mid, int right) {
for (int i = left; i<= right; i++) {
temp[i] = nums[i];
}
int i = left;
int j = mid+1;
for (int k = left; k <= right; k++) {
if (i > mid) {
nums[k] = temp[j++];
ans += 0; // i后面没有元素了，逆序对+0
} else if (j > right) {
nums[k] = temp[i++];
} else if (temp[i] < temp[j]) {
nums[k] = temp[i++];
} else if (temp[i] == temp[j]){
nums[k] = temp[i++];
} else {
ans += (mid - i + 1); // 增加逆序对
nums[k] = temp[j++];
}
}
}
复制代码解法2:
解法1考虑的是，j插入时，根据左数组比j大的值来更新逆序对。
解法2考虑的是，i插入时，根据右数组比i小的值来更新逆序对。
当i、j对应的值相等时，先插入了i，所以当temp[i]==temp[j]时，比i小的j一定已经插入了，同理，当temp[i] < temp[j]时，比i小的j也一定已经被插入了，所以对于temp[i]<=temp[j]，j的左边都比当前i要小，逆序对的数量等于j左边的元素的数量: j-mid-1
如果j已经全部被插入：此时需要增加逆序对的数量为：right-mid
for (int k = left; k <= right; k++) {
if (i > mid) {
nums[k] = temp[j++];
} else if (j > right) {
nums[k] = temp[i++];
ans += right-mid;
} else if (temp[i] <= temp[j]) {
nums[k] = temp[i++];
ans += j-mid-1;
} else {
nums[k] = temp[j++];
}
}
复制代码计算数组中右侧比当前元素小的个数
leetcode：315. 计算右侧小于当前元素的个数 - 力扣（LeetCode） (leetcode-cn.com)
给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例：
输入：nums = [5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素
复制代码归并排序分成了左右两个有序数组，左数组中一定不存在右侧的比当前元素小，本题就变成了，求归并排序合并时，左数组插入时，右数组当前元素小的个数。利用逆序对的解法2，求右数组比当前元素小的个数。
如果本题换成：数组中左侧比当前元素大的个数，那么就需要用到逆序对的解法1。
同时，本题还考察了知识点：索引数组。
本题要求的是每一个元素，右边比他小的元素的个数，所以归并排序的过程中，关心的是每一个下标，需要对下标构建一个索引数组，每次合并时，比较的是nums的值，更新的是index的下标，tmp也不再保存值而是保存下标。（归并排序时，比较的是值，更新的是值）。
int n = nums.length;
int[] index = new int[n]; // 构建一个索引数组，index[i]表示，数组nums下标i，在排序后的位置为index[i]
int[] tmp = new int[n];
for (int i = 0; i < nums.length; i++) {
index[i] = i;
tmp[i] = i;
}
复制代码那么，当更新时：
int[] count = new int[n]; // count[i] ： nums[i] 右边比nums[i]小的元素个数
private void merge(int left, int mid, int right) {
for (int i = left; i <= right; i++) {
tmp[i] = index[i];
}
int i = left;
int j = mid+1;
// 比较的是值，更新的是index中保存的下标
for (int k = left; k <= right; k++) {
if (i > mid) {
index[k] = tmp[j++];
} else if (j > right) {
index[k] = tmp[i++];
count[index[k]] += right-mid; // 已合并的j都比当前合并的元素i小
} else if (nums[tmp[i]] > nums[tmp[j]]) {
index[k] = tmp[j++];
} else {
index[k] = tmp[i++];
count[index[k]] += (j-mid-1); // 已合并的j都比当前合并的元素i小
}
}
}
复制代码
