KK's blog

每天积累多一些

0%

LeetCode 2089 Find Target Indices After Sorting Array

Posted on Disqus:

LeetCode



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:

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.


Constraints:

1 <= nums.length <= 100 1 <= nums[i], target <= 100

题目大意：

如果数组已排序，求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
32
def 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
46
def 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)

Free mock interview