Python | Leetcode Python题解之第315题计算右侧小于当前元素的个数
题目:
题解:
import numpy as np
from bisect import bisect_leftclass Solution:max_len = 10000c = []buckets = []def countSmaller(self, nums: List[int]) -> List[int]:self.c = [0 for _ in range(len(nums) + 5)]counts = [0 for _ in range(len(nums))]nums = self.discretization(nums)for i in range(len(nums) - 1, -1, -1):num = nums[i]counts[i] = self.query(num-1)self.updateC(num)return countsdef updateC(self, pos):while pos < len(self.c):self.c[pos] += 1pos += self.lowbit(pos)def lowbit(self, x):"""获取更新范围"""return x & (-x)def query(self, pos):"""查询前缀和"""val = 0while pos > 0:val += self.c[pos]pos -= self.lowbit(pos)return valdef getMappingList(self, nums):"""列表去重排序"""return list(sorted(set(nums)))def discretization(self, nums):"""将nums进行离散化变换"""mapping = self.getMappingList(nums)return [bisect_left(mapping, num) + 1 for num in nums]