A.每日一题：2089. 找出数组排序后的目标下标

题目链接：2089. 找出数组排序后的目标下标（简单）

算法原理：

解法一：二分查找

6ms击败14.34%

时间复杂度O(n logn)

这是典型的 “最左端点模型”，可以通过最左端点模型找到等于 target 的第一个点，然后往后遍历，直至不等于 target，这个过程中记录下标，并返回，当然，如果没有 target，就返回空列表即可，下面这篇博客有系统的 二分查找模型知识⬇️

一轮复习——D.二分查找模型总结

解法二：一次遍历

0ms击败100.00%

时间复杂度O(N)

记录 nums 中小于 target 的个数为 less，等于 target 的个数为 equal

排序后，由于相同的数是连续的，那么等于 target 的第一个数的下标就是 less，最后一个数的下标就是 less+equal-1

Java代码：

class Solution { //2089. 找出数组排序后的目标下标 //解法一：二分查找 public List<Integer> targetIndices(int[] nums, int target) { //二分查找最左端点模型 int n=nums.length; List<Integer> ret=new ArrayList<>(); Arrays.sort(nums); int left=0,right=n-1; while(left<right){ int mid=left+(right-left)/2; if(nums[mid]<target) left=mid+1; else right=mid; } if(nums[left]!=target) return ret; while(left<n&&nums[left]==target) ret.add(left++); return ret; } }

class Solution { //2089. 找出数组排序后的目标下标 //解法二：一次遍历 public List<Integer> targetIndices(int[] nums, int target) { int less=0,equal=0; for(int x:nums){ if(x<target) less++; else if(x==target) equal++; } List<Integer> ret=new ArrayList<>(); for(int i=0;i<equal;i++) ret.add(less+i); return ret; } }