315.计算右侧小于当前元素的个数

链接：315.计算右侧小于当前元素的个数
难度：Hard
标签：树状数组、线段树、数组、二分查找、分治、有序集合、归并排序
简介：给定一个整数数组 nums，按要求返回一个新数组  counts。数组 counts 有该性质： counts[i] 的值是   nums[i] 右侧小于  nums[i] 的元素的数量。

题解 1 - typescript

• 编辑时间：2020-07-11
• 执行用时：828ms
• 内存消耗：38.8MB
• 编程语言：typescript
• 解法介绍：双重循环。

function countSmaller(nums: number[]): number[] {
  const len = nums.length;
  const res: number[] = [];
  for (let i = 0; i < len; i++) {
    let c = 0;
    const num = nums[i];
    for (let j = i + 1; j < len; j++) {
      if (num > nums[j]) cpp;
    }
    res[i] = c;
  }
  return res;
}

题解 2 - typescript

• 编辑时间：2021-05-14
• 执行用时：368ms
• 内存消耗：64.5MB
• 编程语言：typescript
• 解法介绍：分治，统计两部分中下标排序时计算。

function countSmaller(nums: number[]): number[] {
  const len = nums.length;
  if (len === 0) return [];
  const list = new Array(len).fill(0).map((_, i) => i);
  const ans = new Array(len).fill(0);
  const mergeSort = (left: number, right: number): void => {
    if (left === right) return;
    const mid = (left + right) >> 1;
    mergeSort(left, mid);
    mergeSort(mid + 1, right);
    const temp = list.slice(left, mid + 1);
    let p1 = 0,
      end1 = mid - left,
      p2 = mid + 1,
      i = left;
    while (p1 <= end1) {
      if (p2 > right || nums[temp[p1]] <= nums[list[p2]]) {
        const index = temp[p1++];
        list[i++] = index;
        ans[index] += p2 - mid - 1;
      } else {
        list[i++] = list[p2++];
      }
    }
  };
  mergeSort(0, len - 1);
  return ans;
}