315. Count of Smaller Numbers After Self
Đề Bài
Given an integer array nums, return an integer array counts 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
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(log n)
💾 Không gian
O(n)
Lời Giải
Python
0315-count-of-smaller-numbers-after-self.py
class SegmentTree:
def __init__(self, maxVal):
self.tree = [0] * 4 * maxVal
def update(self, node, left, right, index):
if not left <= index <= right:
return
if left == right:
self.tree[node] += 1
return
mid = (left + right) >> 1
self.update(node * 2, left, mid, index)
self.update(node * 2 + 1, mid + 1, right, index)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def sumRange(self, node, left, right, qleft, qright):
if right < qleft or qright < left:
return 0
if qleft <= left and right <= qright:
return self.tree[node]
mid = (left + right) >> 1
sumLeft = self.sumRange(node * 2, left, mid, qleft, qright)
sumRight = self.sumRange(node * 2 + 1, mid + 1, right, qleft, qright)
return sumLeft + sumRight
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
n = len(nums)
for i in range(n):
nums[i] += 10**4 + 1
maxVal = max(nums)
res = [0 for _ in range(n)]
it = SegmentTree(maxVal)
for i in range(n - 1, -1, -1):
res[i] = it.sumRange(1, 1, maxVal, 1, nums[i] - 1)
it.update(1, 1, maxVal, nums[i])
return res