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

🟢   🔖  数组 哈希表 计数 排序  🔗 力扣 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+	🟢	🀄️ 🔗