这道题的最简单算法,时间复杂度O(nlogn):
public List<Integer> targetIndices(int[] nums, int target) { Arrays.sort(nums); List<Integer> res = new ArrayList<>(); for(int i=0;i<nums.length;i++){ if(nums[i]==target) res.add(i); } return res; }
把查找数字那部分binary search的算法,总的时间复杂度还是O(nlogn):
public List<Integer> targetIndices(int[] nums, int target) { Arrays.sort(nums); List<Integer> res = new ArrayList<>(); int l = 0, r = nums.length-1; while(l<=r){ int mid = (l+r)/2; if(nums[mid]<target){ l = mid+1; }else if(nums[mid]>target){ r = mid -1; }else{ int i = mid; while(i>=0){ if(nums[i]==target){ res.add(0, i); } i--; } i = mid+1; while(i<nums.length){ if(nums[i]==target){ res.add(i); } i++; } return res; } } return res; }
不需要排序的算法,时间复杂度O(n)
public List<Integer> targetIndices(int[] nums, int target) { int belowTCount=0, tCount=0; for(int n : nums){ if(n<target) belowTCount++; else if(n==target) tCount++; } List<Integer> ans = new ArrayList<>(); for(int t=0;t<tCount;t++) ans.add(belowTCount++); return ans; }