Question
Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].
Return the answer in an array.
Example 1:
Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation:
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3).
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1).
For nums[3]=2 there exist one smaller number than it (1).
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).
Plain Text
복사
Example 2:
Input: nums = [6,5,4,8]
Output: [2,1,0,3]
Plain Text
복사
Example 3:
Input: nums = [7,7,7,7]
Output: [0,0,0,0]
Plain Text
복사
My Answer
class Solution:
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
countArr = []
count = 0
for i in range(len(nums)):
excludedArr = [x for x in nums if x != nums[i]]
for num in excludedArr:
if num < nums[i]:
count+=1
countArr.append(count)
count = 0
return countArr
Python
복사
Optimized Version
class Solution:
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
dict = {}
sortedNums = sorted(nums)
for i, n in enumerate(sortedNums):
if n not in dict: #중복숫자 있는 경우 덮어씌우는것 방지
dict[n] = i
res = []
for i in nums:
res.append(dict[i])
return res
Python
복사
enumerate함수
인덱스와 원소를 동시에 접근하면서 루프를 돌릴 수 있음.
>>> for entry in enumerate(['A', 'B', 'C']):
... print(entry)
...
(0, 'A')
(1, 'B')
(2, 'C')
Python
복사
이 버전에서는 직접 비교하고 개수를 세는것이 아님
정렬한 이후에 숫자의 인덱스를 dict에 저장(dict는 조회속도가 빠르기 때문)
nums를 순회하며 숫자를 넣으면 저장된 index가 조회됨 → 순서대로 result 배열에 append
