[LeetCode][Python3] 315. Count of Smaller Numbers After Self

Problem :

https://leetcode.com/problems/count-of-smaller-numbers-after-self/

My Solution :

class Solution:

def countSmaller(self, nums: List[int]) -> List[int]:

def bin_search(arr, x):

if not arr:

return 0

if x <= arr[0]:

return 0

if x > arr[-1]:

return len(arr)

lo, high = 0, len(arr)

while lo < high:

mid = (lo + high) // 2

if arr[mid] < x:

lo = mid + 1

else:

high = mid

return lo

indexes = []

sorted_nums = []

for n in nums[::-1]:

idx = bin_search(sorted_nums, n)

sorted_nums.insert(idx, n)

indexes.append(idx)

return indexes[::-1]

Comment :

입력 array를 거꾸로 순회하면서 새로운 array에 정렬을 유지하며 삽입할 때, 그 index가 해답이 된다.

[5,2,6,1] 을 예로 설명하면

[] -> 1을 index 0에 삽입

[1] -> 6을 index 1에 삽입

[1, 6] -> 2를 index 1에 삽입

[1, 2, 6] -> 5를 index 2에 삽입

따라서 [2,1,1,0]이 정답이 된다.

삽입할 index를 찾는 방법은 앞에서부터 O(N)으로 찾아도 되겠지만 이진 탐색을 하면 O(logN)으로 찾을 수 있다.

직접 구현한 이진 탐색 bin_search가 별로 효율적이지 않은가보다. 파이썬 표준 라이브러리 bisect를 사용하니 시간이 더 단축되었다.

My Solution2:

from bisect import bisect_left

class Solution:

def countSmaller(self, nums: List[int]) -> List[int]:

indexes = []

sorted_nums = []

for n in nums[::-1]:

idx = bisect_left(sorted_nums, n)

sorted_nums.insert(idx, n)

indexes.append(idx)

return indexes[::-1]