分治思想
解题思路
利用归并排序将序列降序排列；
再合并的时候进行计算右侧小于当前元素的个数，由于是降序排列，如果 左侧元素 i 大于 右侧元素 j 说明 元素 i 大于右侧所有的元素，则小于 元素 i 的右侧元素数量为
right - j + 1；此题的难度在于：如果在前面的合并之后，如果元素位置变动了，那么对应的 计数数组 的位置就变化了，我们可以利用 map 来记录元素和 count 的映射关系（也可以利用索引数组）；
在纸上画一下执行步骤，更助于理解，map 的方式更好理解
复杂度
-
时间复杂度：
O(NlogN)，数组的元素个数是 N ，递归执行分治法，时间复杂度是O(logN) -
空间复杂度：
O(N)
代码实现（map）
map 版本的不能通过有 重复元素 的测试用例，只是用来理解
索引数组；
var countSmaller = function (nums) {
let len = nums.length;
let map = new Map(); // 记录 num 和右侧小于 num 的元素数量
for (let i = 0; i < nums.length; i++) {
map.set(nums[i], 0);
}
const merge = (nums, left, mid, right) => {
let i = left;
let j = mid + 1;
let k = 0;
const tmpArr = new Array(right - left + 1); // 临时数组用于存储一次归并过程中排序好的元素
while (i <= mid && j <= right) {
if (nums[i] > nums[j]) {
map.set(nums[i], map.get(nums[i]) + (right - j + 1)); //右半部分小于nums[i]元素的数目
tmpArr[k++] = nums[i++];
} else {
tmpArr[k++] = nums[j++];
}
}
while (i <= mid) {
tmpArr[k++] = nums[i++];
}
while (j <= right) {
tmpArr[k++] = nums[j++];
}
for (let k = 0; k < right - left + 1; k++) {
nums[left + k] = tmpArr[k];
}
};
const mergeSort = (nums, left, right) => {
if (left >= right) return;
let mid = (left + right) >> 1;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, right);
};
mergeSort(nums, 0, len - 1);
return [...map].map(([key, count]) => count);
};
代码实现（索引数组）
var countSmaller = function (nums) {
let len = nums.length;
let index = new Array(len); // 原数组的索引数组，存储着原数组中每个元素对应的下标
let count = new Array(len).fill(0); // 记录题目中所求的 count[i]
for (let i = 0; i < nums.length; i++) {
index[i] = i;
}
const merge = (nums, left, mid, right) => {
let i = left;
let j = mid + 1;
let k = 0;
const tmpArr = new Array(right - left + 1); // 临时数组用于存储一次归并过程中排序好的元素
const tmpIndex = new Array(right - left + 1);//临时数组的索引数组，存储这临时数组中每个元素对应的下标
while (i <= mid && j <= right) {
if (nums[i] > nums[j]) {
count[index[i]] += right - j + 1; //右半部分小于nums[i]元素的数目
tmpIndex[k] = index[i]; //记录元素位置的改变
tmpArr[k++] = nums[i++];
} else {
tmpIndex[k] = index[j];
tmpArr[k++] = nums[j++];
}
}
while (i <= mid) {
tmpIndex[k] = index[i];
tmpArr[k++] = nums[i++];
}
while (j <= right) {
tmpIndex[k] = index[j];
tmpArr[k++] = nums[j++];
}
for (let k = 0; k < right - left + 1; k++) {
nums[left + k] = tmpArr[k];
index[left + k] = tmpIndex[k];
}
};
const mergeSort = (nums, left, right) => {
if (left >= right) return;
let mid = (left + right) >> 1;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, right);
};
mergeSort(nums, 0, len - 1);
return count;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 LCR 170. 交易逆序对的总数
上一篇
评论
