LeetCode 题解工作台
找出数组排序后的目标下标
给你一个下标从 0 开始的整数数组 nums 以及一个目标元素 target 。 目标下标 是一个满足 nums[i] == target 的下标 i 。 将 nums 按 非递减 顺序排序后，返回由 nums 中目标下标组成的列表。如果不存在目标下标，返回一个 空 列表。返回的列表必须按 递增 顺…
3
题型
5
代码语言
3
相关题
当前训练重点
简单 · 二分·搜索·答案·空间
答案摘要
将数组 `nums` 排序后，遍历数组，找出所有等于 `target` 的元素的下标，将其加入结果数组中。 时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 为数组 `nums` 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个下标从 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 <= 1001 <= nums[i], target <= 100
解题思路
方法一：排序
将数组 nums 排序后，遍历数组，找出所有等于 target 的元素的下标，将其加入结果数组中。
时间复杂度 ，空间复杂度 。其中 为数组 nums 的长度。
class Solution:
def targetIndices(self, nums: List[int], target: int) -> List[int]:
nums.sort()
return [i for i, v in enumerate(nums) if v == target]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the candidate understands binary search and how it can be applied to find the target indices efficiently after sorting.
- question_mark
Evaluate if the candidate considers edge cases like no target in the array or all elements being the target.
- question_mark
Observe whether the candidate can justify their choice of sorting and binary search as a solution pattern.
常见陷阱
外企场景- error
Overlooking the requirement to sort the array first before applying binary search can lead to incorrect results.
- error
Failing to handle edge cases, such as when the target element is not present in the array, or when all elements are the target.
- error
Not returning the indices in the correct order or leaving out some of the indices if there are multiple occurrences of the target.
进阶变体
外企场景- arrow_right_alt
Modify the problem to handle a larger array or larger range of target values to test efficiency and edge case handling.
- arrow_right_alt
Extend the problem to allow for reverse sorting of the array, and adjust the approach for finding the target indices accordingly.
- arrow_right_alt
Introduce a variant where you need to find the indices of multiple target values instead of a single target.