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

难度: Easy

给你一个下标从 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

Submission

运行时间: 24 ms

内存: 15.9 MB

class Solution:
    def targetIndices(self, nums: List[int], target: int) -> List[int]:
        return [i for i, val in enumerate(sorted(nums)) if val == target]

Explain

此题解首先对输入数组进行排序，然后使用列表推导（list comprehension）结合enumerate函数来遍历排序后的数组，寻找等于目标值target的元素的下标。若找到，则收集这些下标；若未找到，则返回空列表。最终返回的下标列表是按照升序排列的，因为是在已排序的数组上进行的遍历。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def targetIndices(self, nums: List[int], target: int) -> List[int]:
        # 对数组nums进行排序
        sorted_nums = sorted(nums)
        # 使用列表推导和enumerate寻找所有值等于target的下标
        return [i for i, val in enumerate(sorted_nums) if val == target]

Explore

在这个问题中，虽然使用二分查找方法可以更快地找到一个等于目标值的元素（时间复杂度为O(log n)），但是二分查找只能直接定位到目标值的一个位置，而不是所有位置。如果目标值在数组中出现多次，二分查找后还需额外的步骤来确定所有相同元素的范围，这可能涉及向左和向右扫描直到找不到更多的目标值。使用列表推导和enumerate可以在一次遍历中直接收集所有目标值的索引，特别是当目标值频繁出现时，这种方法在代码编写上更直观且易于实现。

如果目标值target在数组中连续出现并集中在一个区间，可以使用改进的二分查找方法来先找到第一个和最后一个target的下标，从而定位整个区间。首先使用二分查找定位到一个target的下标，然后向左和向右使用二分查找方法分别找到第一个和最后一个target的位置。这样可以在O(log n)的时间复杂度内找到整个target的区间，而不需要遍历整个数组。这种方法在target值分布不均匀时尤其高效。

在实际编程中，可以在进行任何查找操作之前先检查target值是否可能存在于数组中。这可以通过检查数组的最小值和最大值来实现。如果target小于数组的最小值或大于最大值，则可以直接返回空列表而无需进一步处理。这种方法简单且有效，可以避免在target明显不在数组范围内时进行不必要的计算。

如果输入数组已知为非递减顺序（即已经排序），则无需再次排序，这可以显著提高算法的效率。排序步骤通常是算法中最耗时的部分，具有O(n log n)的时间复杂度。省略这一步骤后，可以直接进行查找操作，如使用二分查找来快速定位目标值的位置，从而将整体时间复杂度降低到O(log n)。这种省略不仅提高了算法的执行速度，还降低了运算资源的消耗。