315. Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

My Answer 1: Time Limit Exceeded (14 / 65 test cases passed.)

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        result = []
        
        for i in range(len(nums)):
            count = 0
            for j in range(i+1, len(nums)):
                if nums[i] > nums[j]:
                    count += 1
            result.append(count)
        
        return result

당연히 첨엔 문제 고대로 돌리는 방식이 생각났다.
근데 14개만 통과시키고 타임리밋이라는 점~

창의력이 부족한건지.. 머리가 안돌아가서 루션이를 봤다

Hashmap

Solution 1: Time Limit Exceeded (32 / 65 test cases passed.)

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        nums = nums[::-1]
        min_v = min(nums) if nums else 0
        
        import collections
        record = collections.defaultdict(int)
        
        res = []
        for n in nums:
            cnt = 0
            for target in range(min_v,n):
                if target in record:
                    cnt += record[target]
            res.append(cnt)
            record[n]+=1
        return res[::-1]

이게 젤 이해 잘가는 루션이었는데 타임리밋임...

nums 를 reverse 해주고 record 라는 해시맵 역할의 딕셔너리를 만들어서 count 하는 식

min_v 에 min(nums) 를 넣어줘서
min_v ~ n 까지의 숫자들 중에 record 에 있는 숫자들만 cnt 에 더해줌 => n 보다 작은 숫자의 개수

SegmentTree

Solution 2: Runtime: 8300 ms - 5.00% / Memory Usage: 38 MB - 6.52%

class SegmentTreeNode:
    def __init__(self, low, high):
        self.low = low
        self.high = high
        self.left = None
        self.right = None
        self.cnt = 0
        
class Solution: 
    def _build(self, left, right):
        root = SegmentTreeNode(self.nums[left], self.nums[right])
        if left == right:
            return root
        
        mid = (left+right)//2
        root.left = self._build(left, mid)
        root.right = self._build(mid+1, right)
        return root
    
    def _update(self, root, val):
        if not root:
            return 
        if root.low <= val <= root.high:
            root.cnt += 1
            self._update(root.left, val)
            self._update(root.right, val)
            
    def _query(self, root, lower, upper):
        if lower <= root.low and root.high <= upper:
            return root.cnt
        if upper < root.low or root.high < lower:
            return 0
        return self._query(root.left, lower, upper) + self._query(root.right, lower, upper)
    
	# O(nlogn)
    def countSmaller(self, nums: List[int]) -> List[int]:
        nums = nums[::-1]
        self.nums = sorted(list(set(nums)))
        root = self._build(0, len(self.nums)-1)  if nums else None
        
        res = []
        for n in nums:
            res.append(self._query(root,float('-inf'),n-1)) 
            self._update(root, n)
        return res[::-1]

이게 트리까지 나올 일이었군요..

nums 를 reverse 해준 다음 중복 없애고 sort 한 nums 값을 self.nums 에 넣어주는데...
build 에 update, query 너무 끔찍스러움

Merge Sort

Solution 3: Runtime: 2708 ms - 14.29% / Memory Usage: 92.4 MB - 5.00%

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        nums = nums[::-1]
        nums = [(n,i) for i,n in enumerate(nums)]
        res = [0]*len(nums)
        
        def mergesort(l,r):
            if l == r:
                return 
            mid = (l+r)//2
            mergesort(l,mid)
            mergesort(mid+1,r)
            
            i = l
            # O(n)
            for j in range(mid+1,r+1):
                while i < mid+1 and nums[i][0] < nums[j][0]:
                    i += 1
                res[nums[j][1]] += i-l
       
            nums[l:r+1] = sorted(nums[l:r+1])
            
        mergesort(0,len(nums)-1) if nums else None
        return res[::-1]

SegmentTree 보다 런타임은 좋아보이는데 이것도 완전 이해는 안된다...^^

left, mid, right 를 이용해서 반씩 나눈 후 merge sort 함

nums[j][0] => nums 값 | nums[j][1] => nums 의 인덱스 값

right 만 보면서 작은 값들의 개수를 res 에 넣는 거 같은데.....

sorted(nums[l:r+1]) 이건 왜 해주는지...? 이해가 잘 안됨

그냥 이 문제 버릴게요^^