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

发表于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

LeetCode每日一题，1365. How Many Numbers Are Smaller Than the Current Number

先看题目描述

Bn7h9A.png

大意就是给定一个数组 nums，对于其中每个数 nums[i]，让我们统计比它小的所有数字的数目

算法和思路

哈希表

思路就是先复制一个和 nums 一样的数组 temp，然后对 temp 进行排序，然后遍历 temp，每当遍历到一个和前面数字不一样的数时，就用哈希表记录下该数字和其下标，其下标就是小于它的数字的数目。最后遍历 nums 数组中的每个数 nums[i]，res[i] 就等于哈希表中 nums[i] 索引对应的 value值，最后返回 res即可

计数排序

注意到数组元素的值域为 [0, 100]，所以可以考虑建立一个频次数组 cnt ，cnt[i] 表示数字 i 出现的次数。那么对于数字 i 而言，小于它的数目就为 cnt[0] + cnt[1] + … + cnt[i - 1] 的总和；具体地，构建好频次数组 cnt 后，我们遍历 cnt 数组中的每个数 cnt[i]，对其执行 cnt[i] = cnt[i] + cnt[i - 1] 操作，那么此时 cnt[i] 就表示小于等于 i 的数字的数目，res[i] 就与 cnt[nums[i] - 1] 对应，最后返回 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
29
30
import java.util.*;

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];
        int[] temp = new int[len];
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        System.arraycopy(nums, 0, temp, 0, len);
        Arrays.sort(temp);
        if (temp[0] == temp[len - 1]) {
           return res;
        }
        map.put(temp[0], 0);
        int index = 1;
        while (index < len) {
            while (index < len && temp[index] == temp[index - 1]) {
                index++;
            }
            if (index < len) {
                map.put(temp[index], index);
            }
            index++;
        }
        for (int i = 0; i < len; i++) {
            res[i] = map.get(nums[i]);
        }
        return res;
    }
}

计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];
        int[] cnt = new int[101];
        for (int num : nums) {
            cnt[num]++;
        }
        for (int i = 1; i <= 100; i++) {
            cnt[i] += cnt[i - 1];
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] > 0) {
                res[i] = cnt[nums[i] - 1];
            }
        }
        return res;
    }
}