跳转至

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

题目描述

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

 

示例 1：

输入：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：

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

示例 3：

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

 

提示：

  • 2 <= nums.length <= 500
  • 0 <= nums[i] <= 100

解法

方法一：排序 + 二分查找

思考

对每个 \(x\) 统计严格更小的元素个数。双重循环在 \(n \le 500\) 可过，但排序后 \(x\) 的名次就是答案。复制一份升序数组，再对每个 \(x\) 二分第一个不小于它的位置，该下标即更小元素个数。

我们可以将数组 \(nums\) 复制一份，记为 \(arr\)，然后对 \(arr\) 进行升序排序。

接下来，对于 \(nums\) 中的每个元素 \(x\)，我们可以通过二分查找的方法找到第一个大于等于 \(x\) 的元素的下标 \(j\)，那么 \(j\) 就是比 \(x\) 小的元素的个数，我们将 \(j\) 存入答案数组中即可。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是数组 \(nums\) 的长度。

1
2
3
4
class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        arr = sorted(nums)
        return [bisect_left(arr, x) for x in nums]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] arr = nums.clone();
        Arrays.sort(arr);
        for (int i = 0; i < nums.length; ++i) {
            nums[i] = search(arr, nums[i]);
        }
        return nums;
    }

    private int search(int[] nums, int x) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> arr = nums;
        sort(arr.begin(), arr.end());
        for (int i = 0; i < nums.size(); ++i) {
            nums[i] = lower_bound(arr.begin(), arr.end(), nums[i]) - arr.begin();
        }
        return nums;
    }
};

1
2
3
4
5
6
7
8
9
func smallerNumbersThanCurrent(nums []int) (ans []int) {
    arr := make([]int, len(nums))
    copy(arr, nums)
    sort.Ints(arr)
    for i, x := range nums {
        nums[i] = sort.SearchInts(arr, x)
    }
    return nums
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function smallerNumbersThanCurrent(nums: number[]): number[] {
    const search = (nums: number[], x: number) => {
        let l = 0,
            r = nums.length;
        while (l < r) {
            const mid = (l + r) >> 1;
            if (nums[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    };
    const arr = nums.slice().sort((a, b) => a - b);
    for (let i = 0; i < nums.length; ++i) {
        nums[i] = search(arr, nums[i]);
    }
    return nums;
}

方法二：计数排序 + 前缀和

思考

值域只有 \([0,100]\)，不必比较排序。计数后再做前缀和，\(s[x]\) 即为小于 \(x\) 的个数，线性扫一遍原数组即可作答，去掉 \(O(n\log n)\) 的排序。

我们注意到数组 \(nums\) 中的元素的范围是 \([0, 100]\)，因此我们可以使用计数排序的方法，先统计数组 \(nums\) 中每个元素的个数。然后对计数数组进行前缀和计算，最后遍历数组 \(nums\)，对于每个元素 \(x\)，我们直接将计数数组中下标为 \(x\) 的元素的值加入答案数组即可。

时间复杂度 \(O(n + M)\)，空间复杂度 \(O(M)\)，其中 \(n\) 和 \(M\) 分别是数组 \(nums\) 的长度和最大值。

1
2
3
4
5
6
7
class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        cnt = [0] * 102
        for x in nums:
            cnt[x + 1] += 1
        s = list(accumulate(cnt))
        return [s[x] for x in nums]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] cnt = new int[102];
        for (int x : nums) {
            ++cnt[x + 1];
        }
        for (int i = 1; i < cnt.length; ++i) {
            cnt[i] += cnt[i - 1];
        }
        int n = nums.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = cnt[nums[i]];
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        int cnt[102]{};
        for (int& x : nums) {
            ++cnt[x + 1];
        }
        for (int i = 1; i < 102; ++i) {
            cnt[i] += cnt[i - 1];
        }
        vector<int> ans;
        for (int& x : nums) {
            ans.push_back(cnt[x]);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func smallerNumbersThanCurrent(nums []int) (ans []int) {
    cnt := [102]int{}
    for _, x := range nums {
        cnt[x+1]++
    }
    for i := 1; i < len(cnt); i++ {
        cnt[i] += cnt[i-1]
    }
    for _, x := range nums {
        ans = append(ans, cnt[x])
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function smallerNumbersThanCurrent(nums: number[]): number[] {
    const cnt: number[] = new Array(102).fill(0);
    for (const x of nums) {
        ++cnt[x + 1];
    }
    for (let i = 1; i < cnt.length; ++i) {
        cnt[i] += cnt[i - 1];
    }
    const n = nums.length;
    const ans: number[] = new Array(n);
    for (let i = 0; i < n; ++i) {
        ans[i] = cnt[nums[i]];
    }
    return ans;
}

评论