2089.md

title	description	keywords
2089. 找出数组排序后的目标下标	LeetCode 2089. 找出数组排序后的目标下标题解，Find Target Indices After Sorting Array，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 2089. 找出数组排序后的目标下标 找出数组排序后的目标下标 Find Target Indices After Sorting Array 解题思路 数组 二分查找 排序

2089. 找出数组排序后的目标下标

🟢 Easy  🔖  数组 二分查找 排序  🔗 力扣 LeetCode

题目

You are given a 0-indexed integer array nums and a target element target.

A target index is an index i such that nums[i] == target.

Return a list of the target indices of nums after sortingnums in non-decreasing order. If there are no target indices, return an empty list. The returned list must be sorted in increasing order.

Example 1:

Input: nums = [1,2,5,2,3], target = 2

Output: [1,2]

Explanation: After sorting, nums is [1,2 ,2 ,3,5].

The indices where nums[i] == 2 are 1 and 2.

Example 2:

Input: nums = [1,2,5,2,3], target = 3

Output: [3]

Explanation: After sorting, nums is [1,2,2,3 ,5].

The index where nums[i] == 3 is 3.

Example 3:

Input: nums = [1,2,5,2,3], target = 5

Output: [4]

Explanation: After sorting, nums is [1,2,2,3,5].

The index where nums[i] == 5 is 4.

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i], target <= 100

题目大意

给你一个下标从 0 开始的整数数组 nums 以及一个目标元素 target 。

目标下标 是一个满足 nums[i] == target 的下标 i 。

将 nums 按 非递减 顺序排序后，返回由 nums 中目标下标组成的列表。如果不存在目标下标，返回一个 空列表。返回的列表必须按 递增 顺序排列。

示例 1：

输入： nums = [1,2,5,2,3], target = 2

输出：[1,2]

解释： 排序后，nums 变为 [1,2 ,2 ,3,5] 。

满足 nums[i] == 2 的下标是 1 和 2 。

示例 2：

输入： nums = [1,2,5,2,3], target = 3

输出：[3]

解释： 排序后，nums 变为 [1,2,2,3 ,5] 。

满足 nums[i] == 3 的下标是 3 。

示例 3：

输入： nums = [1,2,5,2,3], target = 5

输出：[4]

解释： 排序后，nums 变为 [1,2,2,3,5] 。

满足 nums[i] == 5 的下标是 4 。

示例 4：

输入： nums = [1,2,5,2,3], target = 4

输出：[]

解释： nums 中不含值为 4 的元素。

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i], target <= 100

解题思路

需要找出数组 nums 排序后，目标值 target 的所有索引位置。

如果直接对数组排序再查找索引，效率较低。因此，可以通过统计的方式在 不排序 的情况下解决问题。

可以直接统计数组中比 target 小的元素个数，以及等于 target 的元素个数。

因为在排序后的数组中，比 target 小的元素的个数就是 target 出现的最小索引，等于 target 的元素的个数决定了结果的范围。

1. 初始化变量：

   • 定义 smaller 表示比 target 小的元素个数。
   • 定义 equal 表示等于 target 的元素个数。

2. 遍历数组：

   • 如果当前元素小于 target，增加 smaller 的计数。
   • 如果当前元素等于 target，增加 equal 的计数。

3. 生成结果数组：

   • 根据 smaller 和 equal 的值，生成 [smaller, smaller + equal) 范围的索引。

4. 返回结果数组。

复杂度分析

• 时间复杂度：O(n)，其中 n 是 nums 数组的长度，遍历 nums 数组一次。
• 空间复杂度：O(equal)，用于存储结果数组。

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var targetIndices = function (nums, target) {
	let smaller = 0,
		equal = 0;

	// 遍历 nums 统计 smaller 和 equal
	for (let num of nums) {
		if (num < target) {
			smaller++;
		} else if (num === target) {
			equal++;
		}
	}

	// 生成索引数组
	return new Array(equal).fill().map((_, i) => i + smaller);
};

相关题目

题号	标题	题解	标签	难度	力扣
34	在排序数组中查找元素的第一个和最后一个位置	[✓]	数组 二分查找	🟠	🀄️ 🔗
1331	数组序号转换	[✓]	数组 哈希表 排序	🟢	🀄️ 🔗
2942	查找包含给定字符的单词		数组 字符串	🟢	🀄️ 🔗