「每日LeetCode」2020年10月26日

本文最后更新于：2023年3月19日 晚上

Lt1365. 有多少小于当前数字的数字、哈希、计数排序

1365. 有多少小于当前数字的数字

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
以数组形式返回答案。
 示例 1：

1
2
3
4
5
6
7
8
输入：nums = [8,1,2,2,3]
输出：[4,0,1,1,3]
解释：
对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字：（1）。
对于 nums[3]=2 存在一个比它小的数字：（1）。
对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。

示例 2：

1
2
输入：nums = [6,5,4,8]
输出：[2,1,0,3]

示例 3：

1
2
输入：nums = [7,7,7,7]
输出：[0,0,0,0]

思路

暴力遍历

有一种很显而易见的双重遍历方法，选取一个数字，再从头逐个判断是否比当前数字小，计数加入结果。时间复杂度 O(N^2)，空间复杂度 O(1)

哈希+排序

使用哈希表记录原先数组的下标，再使用 sort 排序，计算当前数字前有几个数字比它小，再通过哈表表得到原来的下标，设置对应结果数组的值。时间复杂度 O(NlogN)，空间复杂度 O(N)

计数排序

可以得知 nums 内数字的值范围在 0-100 之间，并不是很大，所以可以通过计数排序的方法得到结果：

  1. 首先创建一个 100 长度的数组，填充 0
  2. 遍历一次数组，将相应的位数计数添加
  3. 可知比当前数小的是当前数之前每一位数计数之和，所以遍历一次临时数组，每一位等于当前位加前一位
  4. 再遍历一次原数组，将临时数组对应的下标的值加入结果数组。这里需要注意，临时数组的意义是，小于等于当前数的数量，所以根据题意应该取的是当前数的上一个，也就是下标减一的那个数对应的值。为了防止 0 这个数下标-1 取到 undefined，需要单独处理。

解答

暴力遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var smallerNumbersThanCurrent = function (nums) {
  const res = [];
  for (const num1 of nums) {
    let count = 0;
    for (const num2 of nums) {
      if (num1 > num2) count++;
    }
    res.push(count);
  }
  return res;
};

哈希+排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var smallerNumbersThanCurrent = function (nums) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (!map.has(nums[i])) map.set(nums[i], [i]);
    else map.set(nums[i], [...map.get(nums[i]), i]);
  }
  nums.sort((a, b) => Number(a) - Number(b));
  const res = Array(nums.length).fill(0);
  let preCount = 0;
  for (let i = 0; i < nums.length; i++) {
    let count = 1;
    while (i < nums.length - 1 && nums[i + 1] == nums[i]) {
      i++;
      count++;
    }
    if (preCount > 0) {
      map.get(nums[i]).forEach((e) => {
        res[e] = preCount;
      });
    }
    preCount += count;
  }
  return res;
};

计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var smallerNumbersThanCurrent = function (nums) {
  const temp = Array(100).fill(0);
  const res = [];
  for (const num of nums) {
    temp[num]++;
  }
  for (let i = 1; i < 100; i++) {
    temp[i] += temp[i - 1];
  }
  for (let i = 0; i < nums.length; i++) {
    res.push(nums[i] ? temp[nums[i] - 1] : 0);
  }
  return res;
};