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

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

分析

• 这道算法题实现起来不难。
• 至少我们可以按着题意，先对数组排序，然后再遍历排序后的数组。这样的时间复杂度是O(nlogn)，主要是排序花时间比较多。
• 是否可以优化呢？
• 是不是一定要排序呢？
• 根据题意，我们需要知道包含几个目标数字，有几个目标数字就需要返回几个数字的下标。
• 排序后，相同数字一定是连续挨着的，所以返回结果要么为空，要么是连续的。
• 那么我们其实仅需要知道有几个目标数字，和第一个目标数字应该放在哪个位置。
• 目标数字排序后放在哪个位置，仅仅需要关心它前面有几个数字，而并不需要前面的数字有序，有点像快速排序的思想。
• 这样我们就仅需要一次遍历，来统计目标数字有几个，以及比目标数字小的数字有几个就可以了，时间复杂度降为O(n)。

题解

java

class Solution {
    public List<Integer> targetIndices(int[] nums, int target) {
        int lessCount = 0;
        int count     = 0;

        for (int num : nums) {
            if (num == target) {
                ++count;
            } else if (num < target) {
                ++lessCount;
            }
        }

        List<Integer> ans = new ArrayList<>(count);
        for (int i = lessCount; i < lessCount + count; ++i) {
            ans.add(i);
        }
        
        return ans;
    }
}

c

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* targetIndices(int* nums, int numsSize, int target, int* returnSize){
    int less_count = 0;
    *returnSize = 0;
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] == target) {
            ++(*returnSize);
        } else if (nums[i] < target) {
            ++less_count;
        }
    }

    int *ans = malloc(*returnSize * sizeof(*ans));
    for (int i = 0; i < (*returnSize); ++i) {
        ans[i] = less_count + i;
    }

    return ans;
}

c++

class Solution {
public:
    vector<int> targetIndices(vector<int>& nums, int target) {
        int lessCount = 0;
        int count = 0;
        for (const int& num : nums) {
            if (num == target) {
                ++count;
            } else if (num < target) {
                ++lessCount;
            }
        }

        vector<int> ans;
        for (int i = lessCount; i < lessCount + count; ++i) {
            ans.push_back(i);
        }

        return ans;
    }
};

python

class Solution:
    def targetIndices(self, nums: List[int], target: int) -> List[int]:
        less_count = 0
        count = 0
        for num in nums:
            if num == target:
                count += 1
            elif num < target:
                less_count += 1
        ans = []
        for i in range(less_count, less_count + count):
            ans.append(i)
        return ans
        

go

func targetIndices(nums []int, target int) []int {
    lessCount := 0
    count := 0
    for _, num := range nums {
        if num == target {
            count++
        } else if num < target {
            lessCount++
        }
    }

    ans := make([]int, count)
    for i := 0; i < count; i++ {
        ans[i] = i + lessCount
    }

    return ans
}

rust

impl Solution {
    pub fn target_indices(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut less_count = 0;
        let mut count = 0;
        nums.iter().for_each(|num| {
            if *num == target {
                count += 1;
            } else if *num < target {
                less_count += 1;
            }
        });
        (less_count..less_count + count).collect()
    }
}

原题传送门：https://leetcode-cn.com/problems/find-target-indices-after-sorting-array/

非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~