LeetCode 솔루션

[7/23] 315. Count of Smaller Numbers After Self

학부유학생 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.07.22 22:15

7,338 조회
1 댓글
0 추천
0 비추천
목록 게시글 쓰기

315. Count of Smaller Numbers After Self

Hard

6063172Add to ListShare

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].

Example 1:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Example 2:

Input: nums = [-1]
Output: [0]

Example 3:

Input: nums = [-1,-1]
Output: [0,0]

Constraints:

1 <= nums.length <= 105
-104 <= nums[i] <= 104

Accepted

238,807

Submissions

566,839

#Google, #Amazon, #Microsoft, #Adobe

링크

https://leetcode.com/problems/count-of-smaller-numbers-after-self/ 1524 회 연결

익명
작성일 2022.07.22 22:15

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        if len(nums) < 2: return [0]
        array = sorted([nums[-1],nums[-2]])
        res = [0]
        if nums[-1] >= nums[-2]: res.append(0)
        else: res.append(1)
        
        for i in range(len(nums)-3, -1, -1):
            res.append(self.left_insert(array, nums[i]))
        return reversed(res)
    def left_insert(self, array, inserting):
        l, r = 0, len(array)-1
        
        while l<r:
            mid = (l+r)//2
            if array[mid] < inserting:
                l = mid + 1
            elif array[mid] >= inserting:
                r = mid
                
        if array[l] > inserting:
            while l > 0 and array[l] == array[l-1]:
                l -= 1
                
        else:
            while l < len(array)-1 and array[l] == array[l+1]:
                l += 1
            l += 1
                
        array.insert(l, inserting)
        
        while l > 0 and array[l] == array[l-1]:
            l -= 1
        return l

Runtime: 7646 ms, faster than 5.01% of Python3 online submissions for Count of Smaller Numbers After Self.
Memory Usage: 31.6 MB, less than 92.65% of Python3 online submissions for Count of Smaller Numbers After Self.
[code=Python 3]class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        if len(nums) < 2: return [0]
        array = sorted([nums[-1],nums[-2]])
        res = [0]
        if nums[-1] >= nums[-2]: res.append(0)
        else: res.append(1)
        
        for i in range(len(nums)-3, -1, -1):
            res.append(self.left_insert(array, nums[i]))
        return reversed(res)
    def left_insert(self, array, inserting):
        l, r = 0, len(array)-1
        
        while l<r:
            mid = (l+r)//2
            if array[mid] < inserting:
                l = mid + 1
            elif array[mid] >= inserting:
                r = mid
                
        if array[l] > inserting:
            while l > 0 and array[l] == array[l-1]:
                l -= 1
                
        else:
            while l < len(array)-1 and array[l] == array[l+1]:
                l += 1
            l += 1
                
        array.insert(l, inserting)
        
        while l > 0 and array[l] == array[l-1]:
            l -= 1
        return l[/code]