How can I optimize the brute-force approach for this problem?

To optimize the brute-force approach, consider sorting the array first and using a hash table or frequency counter to keep track of smaller numbers, reducing the need for repeated comparisons.

What is the optimal time complexity for solving this problem?

The optimal time complexity for solving this problem is O(n log n), achieved by sorting the array and using efficient lookup techniques.

What should I do if all elements in the array are the same?

If all elements are the same, each element will have zero smaller elements, and the output will be an array of zeros.

How does sorting improve the solution for this problem?

Sorting allows you to determine the number of smaller elements efficiently by referencing the sorted order, reducing the time complexity to O(n log n).

Can I use a hash table to solve this problem?

Yes, using a hash table can help track the frequency of elements and allow you to calculate the count of smaller elements for each number more efficiently than brute force.

#1365

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

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

数组哈希表排序计数排序

题目描述

给你一个数组 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

lightbulb

解题思路

方法一：排序 + 二分查找

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

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

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

1

2

3

4

5

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The problem tests the candidate's ability to optimize brute-force solutions using sorting or hashing techniques.
question_mark
Watch for the candidate's approach to handling larger inputs efficiently, such as using sorting or hash tables.
question_mark
The problem is an opportunity to assess familiarity with array manipulation and counting methods.

warning

常见陷阱

外企场景

error
Overcomplicating the problem by attempting to use complex algorithms when a simpler sorting approach is enough.
error
Failing to account for array elements with equal values, which should all have the same smaller count.
error
Neglecting to optimize the brute force approach, which can lead to performance issues on larger datasets.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modifying the array by adding or removing elements and checking if the solution adapts correctly.
arrow_right_alt
Handling edge cases where all elements are the same, requiring the program to output an array of zeros.
arrow_right_alt
Implementing the solution without sorting, using a hash map or frequency counter to reduce the time complexity.

help

常见问题

外企场景

继续练习

#1122 数组的相对排序 #1366 通过投票对团队排名 #1346 检查整数及其两倍数是否存在