Easy

题目描述

给定一个 0 索引的整数数组 nums 和一个目标元素 target。

目标索引是使得 nums[i] == target 的索引 i。

返回将 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。

约束条件：

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

提示：

  • 试着先"排序"数组。
  • 现在找到数组中所有值等于 target 的索引。

解题思路

这道题有两种主要解法，都比较简单直观：

解法一：直接排序法 按照题目提示，先将数组排序，然后遍历找出所有等于 target 的索引。这是最直观的方法，时间复杂度主要由排序决定。

解法二：统计法（优化） 不需要实际排序数组，只需要统计小于 target 的元素个数和等于 target 的元素个数。排序后，target 元素会连续出现，起始位置就是小于 target 的元素个数，结束位置可以通过起始位置加上 target 元素个数计算得出。这种方法时间复杂度更优。

两种解法都能正确解决问题，但统计法在时间复杂度上有优势，特别是当数组较大时。对于本题的约束条件（数组长度最多100），两种方法性能差异不大，但统计法展示了更好的算法思维。

推荐使用统计法，因为它避免了排序操作，时间复杂度更优。

代码实现

class Solution {
public:
    vector<int> targetIndices(vector<int>& nums, int target) {
        int smaller = 0, equal = 0;
        for (int num : nums) {
            if (num < target) smaller++;
            else if (num == target) equal++;
        }
        
        vector<int> result;
        for (int i = smaller; i < smaller + equal; i++) {
            result.push_back(i);
        }
        return result;
    }
};

class Solution:
    def targetIndices(self, nums: List[int], target: int) -> List[int]:
        smaller = sum(1 for num in nums if num < target)
        equal = sum(1 for num in nums if num == target)
        
        return list(range(smaller, smaller + equal))

public class Solution {
    public IList<int> TargetIndices(int[] nums, int target) {
        int smaller = 0, equal = 0;
        foreach (int num in nums) {
            if (num < target) smaller++;
            else if (num == target) equal++;
        }
        
        var result = new List<int>();
        for (int i = smaller; i < smaller + equal; i++) {
            result.Add(i);
        }
        return result;
    }
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var targetIndices = function(nums, target) {
    nums.sort((a, b) => a - b);
    const result = [];
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === target) {
            result.push(i);
        }
    }
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
统计法O(n)O(1)
排序法O(n log n)O(1)

其中 n 为数组长度。统计法只需要遍历一次数组，时间复杂度为 O(n)；排序法需要先排序再遍历，时间复杂度为 O(n log n)。两种方法的空间复杂度都是 O(1)（不考虑输出数组）。

相关题目