1365.md

title	description	keywords
1365. 有多少小于当前数字的数字	LeetCode 1365. 有多少小于当前数字的数字题解，How Many Numbers Are Smaller Than the Current Number，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 1365. 有多少小于当前数字的数字 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number 解题思路 数组 哈希表 计数 排序

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

🟢 Easy  🔖  数组 哈希表 计数 排序  🔗 力扣 LeetCode

题目

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].

Return the answer in an array.

Example 1:

Input: nums = [8,1,2,2,3]

Output: [4,0,1,1,3]

Explanation:

For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3).

For nums[1]=1 does not exist any smaller number than it.

For nums[2]=2 there exist one smaller number than it (1).

For nums[3]=2 there exist one smaller number than it (1).

For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

Example 2:

Input: nums = [6,5,4,8]

Output: [2,1,0,3]

Example 3:

Input: nums = [7,7,7,7]

Output: [0,0,0,0]

Constraints:

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

题目大意

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

解题思路

1. 排序并记录索引：

   • 遍历原始数组，将每个数字和其索引（[num, index]）作为一个元素存入二维数组。
   • 为了高效地统计比每个数字小的数字个数，按照数组的值（num）对二维数组进行升序排序。

2. 遍历排序数组：

   • 如果当前数字和前一个数字不同，则更新小于当前数字的数量为当前索引值。
   • 如果相同，直接使用前一个数字的结果。

3. 回填结果：

   • 根据原始索引，将计算结果填回到原数组的相应位置。

4. 返回结果：

   • 最终更新的原数组即为答案。

复杂度分析

• 时间复杂度：O(n log n)，其中 n 是数组的长度。

  • 排序的时间复杂度为 O(n log n)。
  • 遍历排序后的数组进行结果回填，时间复杂度为 O(n)。

• 空间复杂度：O(n)，存储排序数组副本的开销。

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var smallerNumbersThanCurrent = function (nums) {
	const n = nums.length;

	// 创建 nums 的副本，并记录其原始索引
	const sorted = nums
		.map((num, index) => [num, index])
		.sort((a, b) => a[0] - b[0]);

	// 遍历排序后的数组
	for (let i = 0; i < n; i++) {
		if (i > 0 && sorted[i][0] === sorted[i - 1][0]) {
			// 如果当前数和前一个数相等，那么小于它的数量和前一个数一样
			nums[sorted[i][1]] = nums[sorted[i - 1][1]];
		} else {
			// 否则，小于它的数量就是它在排序数组中的索引
			nums[sorted[i][1]] = i;
		}
	}

	return nums;
};

相关题目

题号	标题	题解	标签	难度	力扣
315	计算右侧小于当前元素的个数		树状数组 线段树 数组 4+	🔴	🀄️ 🔗
2389	和有限的最长子序列		贪心 数组 二分查找 2+	🟢	🀄️ 🔗