2089. 找出数组排序后的目标下标——O(n)做法！

       

        本题要求在一个已排序的数组 nums 中，找出所有等于目标值 target 的元素下标。若不存在这样的元素，则返回 {-1, -1}。解决该问题有两种主要方法：二分查找法和统计计数法。

二分查找法：首先对数组进行排序，然后通过二分查找确定 target 的下界（即第一个大于等于 target 的元素位置）和上界（即最后一个小于等于 target 的元素位置），这两个位置的交集即为所有等于 target 的元素下标。

        二分代码请看34. 在排序数组中查找元素的第一个和最后一个位置——边界问题不清楚？结果不知道是left还是right？四种大小关系不会转化？一篇文章告诉你！-CSDN博客

        采用二分查找法：首先确定大于等于目标值的最小索引，再找出小于等于目标值的最大索引，这两个索引之间的范围即为等于目标值的区间。

class Solution {
public:int lower_bound(vector<int>& nums,int target) {int n = nums.size();int left = 0,right = n - 1;while (left <= right) {int  mid = (right - left) / 2 + left;if (nums[mid] < target) {left = mid + 1;}else{right = mid - 1;}}return left;}vector<int> targetIndices(vector<int>& nums, int target) {ranges::sort(nums);int n = nums.size();int start = lower_bound(nums,target);if (start == n || nums[start] != target) return {};int end = lower_bound(nums,target + 1) - 1;vector<int> ans;for (int i = start;i <= end;i++){ans.emplace_back(i);}return ans;}
};

        时间复杂度：O(nlogn)

        空间复杂度：O(1)       

        统计小于和等于目标值的方法：通过less_count记录小于目标值的元素数量，equal_count记录等于目标值的元素数量。在排序后的数组中，less_count表示第一个目标值的下标，less_count+1表示第二个目标值的下标，依此类推，直到less_count + equal_count - 1。

        例如：

输入：nums = [1,2,5,2,3], target = 2
输出：[1,2]

     

排序后的数组为 [1, 2, 2, 3, 5]，其中 less = 1，equal = 2，最终结果为 [1, 2]。

class Solution {
public:vector<int> targetIndices(vector<int>& nums, int target) {int less_count = 0,equal_count = 0;for (int it:nums) {if (it < target) less_count++;else if (it == target) equal_count++;}vector<int> ans(equal_count);iota(ans.begin(),ans.end(),less_count);return ans;}
};

        时间复杂度：O(n)

        空间复杂度：O(1)