5938. 找出數組排序后的目標下標

給你一個下標從 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

解題思路

以為題目需要將 nums 按 非遞減 順序排序后，返回由 nums 中目標下標組成的列表，因為返回的是進行排序以后的元素下標，而不需要考慮數組元素原來的下標位置，因此我們可以直接對數組進行一次排序，然后對排序以后的數組進行一次遍歷，檢查是否滿足 nums[i] == target，如果滿足則將下標加入結果數組中。

代碼

class Solution {
public:vector<int> targetIndices(vector<int>& nums, int target) {sort(nums.begin(),nums.end());vector<int> res;for (int i = 0; i < nums.size(); ++i) {if (nums[i]==target)res.push_back(i);}return res;}
};

優化思路

不需要進行排序，只需要記錄比target小的元素，就可以獲取到 nums[i] == target，i在數組中的下標

代碼

class Solution {
public:vector<int> targetIndices(vector<int>& nums, int target) {int less(0),e(0);for (int i = 0; i < nums.size(); ++i) {if (nums[i]==target)e++;else if (nums[i]<target)less++;}vector<int> res;for (int i = 0; i < e; ++i) {res.push_back(less+i);}return res;}
};