从零开始学网站建设知乎,安防网站下载,网络建站,社群营销的方法和技巧文章目录 面试题 10.10. 数字流的秩327. 区间和的个数315. 计算右侧小于当前元素的个数 树状数组可以理解一种数的存储格式。 面试题 10.10. 数字流的秩
假设你正在读取一串整数。每隔一段时间#xff0c;你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。 请实现数据结构… 文章目录 面试题 10.10. 数字流的秩327. 区间和的个数315. 计算右侧小于当前元素的个数 树状数组可以理解一种数的存储格式。 面试题 10.10. 数字流的秩
假设你正在读取一串整数。每隔一段时间你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。 请实现数据结构和算法来支持这些操作也就是说 实现 track(int x) 方法每读入一个数字都会调用该方法 实现 getRankOfNumber(int x) 方法返回小于或等于 x 的值的个数。
面试题 10.10. 数字流的秩
class StreamRank {vectorint v;int lowbit(int x) {return x -x;}
public:StreamRank(): v(50002, 0) {}void track(int x) {x; //x 1是因为树状数组处理的元素下标从1开始while (x 50001) {v[x];x lowbit(x);}}int getRankOfNumber(int x) {x;int ans 0;while (x) {ans v[x];x - lowbit(x);}return ans;}
};class StreamRank:def __init__(self):self.l [0]*50002def lowBit(self, x):return x (-x)def track(self, x: int) - None:x 1while x 50001:self.l[x] 1x self.lowBit(x)def getRankOfNumber(self, x: int) - int:x 1ans 0while x:ans self.l[x]x - self.lowBit(x)return ans327. 区间和的个数
给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中值位于范围 [lower, upper] 包含 lower 和 upper之内的 区间和的个数 。 区间和 S(i, j) 表示在 nums 中位置从 i 到 j 的元素之和包含 i 和 j (i ≤ j)。
327. 区间和的个数 区间过大hash然后到树状数组。
class Solution:def countRangeSum(self, nums, lower: int, upper: int) - int:n len(nums)prefixs [0]*nt 0ans 0for i in range(n):t nums[i]prefixs[i] tif lower t upper:ans 1s set()for i in range(n):s.add(prefixs[i])s.add(prefixs[i]-lower)s.add(prefixs[i] - upper)l sorted(s)d {x: i1 for i, x in enumerate(l)} # hash到固定长度trie [0]*(len(d)1) # 树状数组for i in range(n):left, right d[prefixs[i]-upper], d[prefixs[i]-lower]ans self.query(trie, right) - self.query(trie, left-1)self.insert(trie, d[prefixs[i]])return ansdef query(self, trie, x):ans 0while x:ans trie[x]x - x (-x)return ansdef insert(self, trie, x):while x len(trie):trie[x] 1x x (-x)315. 计算右侧小于当前元素的个数
给你一个整数数组 nums 按要求返回一个新数组 counts 。数组 counts 有该性质 counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
315. 计算右侧小于当前元素的个数
class Solution:def countSmaller(self, nums: List[int]) - List[int]:n len(nums)l [0]*20002 # -10000~10000 - 2~20002 因为求小于x的值x2count输入x1ans [0]*nfor i in range(n-1,-1,-1):x nums[i] 10002ans[i] self.count(l, x-1)self.insert(l, x)return ansdef count(self, l, x):ans 0while x:ans l[x]x - self.lowBit(x)return ansdef lowBit(self, x):return x (-x)def insert(self, l, x):while x len(l):l[x] 1x self.lowBit(x)算法学习笔记(2) : 树状数组
