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

🟢   🔖  数组 二分查找 排序  🔗 力扣 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 sortingnumsin 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	查找包含给定字符的单词		数组 字符串	🟢	🀄️ 🔗