問題
配列numsと整数targetが与えられる．numsを昇順に整列したときにnums[i] == targetを満たすインデックスiをすべて求めよ．
1
2
| nums = [1, 2, 5, 2, 3], target = 2
-> sorted nums = [1, 2, 2, 3, 5] -> ans = [1, 2]
|
解法1
言われたとおりにソートしてから位置を探す．ソートに時間がかかって$O(n \log n)$
1
2
3
4
5
6
7
8
| class Solution:
def targetIndices(self, nums: List[int], target: int) -> List[int]:
nums.sort()
ans = []
for i, num in enumerate(nums):
if num == target:
ans.append(i)
return ans
|
解法2
整列後の配列に置いて，targetと等しい要素の位置を決定するのに，targetより大きい要素が整列されている必要はない．「targetより小さい値が何個あるのか」と「targetと等しい値が何個あるのか」で答えは求まる．
numsを端から一舐めすれば十分で$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution:
def targetIndices(self, nums: List[int], target: int) -> List[int]:
cnt = 0
less = 0
for num in nums:
if num == target:
cnt += 1
elif num < target:
less += 1
ans = []
for i in range(cnt):
ans.append(less + i)
return ans
|
出典