[LeetCode][Python3] 315. Count of Smaller Numbers After Self
2019. 3. 28. 02:20 |
프로그래밍/LeetCode
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]
'프로그래밍 > LeetCode' 카테고리의 다른 글
| [LeetCode][Python3] 207. Course Schedule (0) | 2019.03.31 |
|---|---|
| [LeetCode][Python3] 116. Populating Next Right Pointers in Each Node (0) | 2019.03.30 |
| [LeetCode][Python3] 208. Implement Trie (Prefix Tree) (1) | 2019.03.30 |
| [LeetCode][Python3] 239. Sliding Window Maximum (0) | 2019.03.29 |
| [LeetCode][Python3] 395. Longest Substring with At Least K Repeating Characters (0) | 2019.03.28 |
| [LeetCode][Python3] 73. Set Matrix Zeroes (0) | 2019.03.27 |
| [LeetCode][Python3] 329. Longest Increasing Path in a Matrix (0) | 2019.03.27 |
| [LeetCode][Python3] 264. Ugly Number II (0) | 2019.03.26 |
최근에 달린 댓글 최근에 달린 댓글