05 August 2008
一个索引为 0 的整数数组 nums 和一个目标元素 target。
目标索引是索引 i 使得 nums[i] == 目标。
在以非递减顺序对 nums 进行排序后，返回 nums 的目标索引列表。如果没有目标索引，则返回一个空列表。返回的列表必须按升序排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Example 1:
Input: nums = [1,2,5,2,3], target = 2
Output: [1,2]
Explanation: After sorting, nums is [1,2,2,3,5].
The indices where nums[i] == 2 are 1 and 2.
Example 2:
Input: nums = [1,2,5,2,3], target = 3
Output: [3]
Explanation: After sorting, nums is [1,2,2,3,5].
The index where nums[i] == 3 is 3.
Example 3:
Input: nums = [1,2,5,2,3], target = 5
Output: [4]
Explanation: After sorting, nums is [1,2,2,3,5].
The index where nums[i] == 5 is 4.
排序
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public List<Integer> targetIndices(int[] nums, int target) {
Arrays.sort(nums);
ArrayList<Integer> arrList = new ArrayList<Integer>();
for(int i=0; i<nums.length; i++){}
if(nums[i] == target)
arrList.add(i);
if(nums[i] > target)
break;
}
return arrList;
}
}
binary search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public List<Integer> targetIndices(int[] nums, int target) {
Arrays.sort(nums);
List<Integer> list = new ArrayList<>();
int left = 0;
int right = nums.length-1;
while(left <= right){
int mid = (left+right)/2;
if(target > nums[mid]){
left = mid+1;
}
else if(target < nums[mid]){
right = mid-1;
}
else{
int first = mid, last = mid;
while(first-1 >= 0 && nums[first-1]==target){
first--;
}
while(last+1<nums.length && nums[last+1]==target){
last++;
}
for(int i=first; i<=last; i++){
list.add(i);
}
return list;
}
}
return list;
}
}