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 博客原创~
