<div>
You are given a 0-indexed integer array nums and a target element target.
A target index is an index i such that nums[i] == target.
Return a list of the target indices of nums after sorting nums in non-decreasing order. If there are no target indices, return an empty list. The returned list must be sorted in increasing order.
Example 1:
<pre>Input: nums = [1,2,5,2,3], target = 2 Output: [1,2] Explanation: After sorting, nums is [1,<u>2</u>,<u>2</u>,3,5]. The indices where nums[i] == 2 are 1 and 2. </pre>
Example 2:
<pre>Input: nums = [1,2,5,2,3], target = 3 Output: [3] Explanation: After sorting, nums is [1,2,2,<u>3</u>,5]. The index where nums[i] == 3 is 3. </pre>
Example 3:
<pre>Input: nums = [1,2,5,2,3], target = 5 Output: [4] Explanation: After sorting, nums is [1,2,2,3,<u>5</u>]. The index where nums[i] == 5 is 4. </pre>
Constraints:
1 <= nums.length <= 1001 <= nums[i], target <= 100
</div>
题目大意：
如果数组已排序，求target对应的所有下标。
解题思路：
这道题是Easy题，也是Q&A中被问到的，Binary Search不是最优解，但是可以用它作为解法研究。
解题步骤：
标准binary search
注意事项：
N/A
Python代码：
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
32def targetIndices(self, nums: List[int], target: int) -> List[int]:
sorted_nums = sorted(nums)
target_index = self.binary_search(sorted_nums, target)
res = []
print(target_index)
for i in range(target_index - 1, -1, -1):
if sorted_nums[i] == target:
res.append(i)
res = res[::-1]
for i in range(target_index, len(sorted_nums)):
if sorted_nums[i] == target:
res.append(i)
return res
def binary_search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = start + (end - start) // 2
if target < nums[mid]:
end = mid
else:
start = mid
if nums[end] == target:
return end
elif nums[start] == target:
return start
else:
return -1
算法II解题思路：
first_postition & last position
Python代码：
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
42
43
44
45
46def targetIndices(self, nums: List[int], target: int) -> List[int]:
sorted_nums = sorted(nums)
target_upper_index = self.last_position(sorted_nums, target)
target_lower_index = self.first_position(sorted_nums, target)
res = [i for i in range(target_lower_index, target_upper_index + 1)]
return [] if target_upper_index == -1 else res
def first_position(self, nums: List[int], target: int) -> int:
if not nums:
return -1
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = start + (end - start) // 2
if target < nums[mid]:
end = mid
elif target > nums[mid]:
start = mid
else:
end = mid
if nums[start] == target:
return start
elif nums[end] == target:
return end
else:
return -1
def last_position(self, nums: List[int], target: int) -> int:
if not nums:
return -1
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = start + (end - start) // 2
if target < nums[mid]:
end = mid
elif target > nums[mid]:
start = mid
else: # Depends on the target on the right side or left side. For fist pos, use end = mid
start = mid
if nums[end] == target:
return end
elif nums[start] == target:
return start
else:
return -1
算法分析：
时间复杂度为O(nlogn)，空间复杂度O(n)
