-
海量积分排序的二分实现
简单描述下问题：有一个网站，现在有很多用户，每个用户有一个积分，要求在用户登录时显示用户的积分排名，用户的积分会有变动。注意考虑数据量比较大的场景。 原理是以树的方式来分解排名的计算。参考在这里。 实际代码分为三部分： 查询某个积分的排名 更新积分 构造积分树 查询积分排名 原理是计算所有右子树或者同级节点的和，再加1。每个节点包含当前积分或者积分段内的用户总数。右子树或者同级节点代表大于指定积分的积分节点。排名的实际含义就是计算所有大于自己积分的人的总数。最后加1是因为大于最大积分的人的总数为0，但是排名不能为0，所以实际显示是必须加1的。 这块实际依赖树的结构，可能是数组或者是链表，但通用逻辑如下（递归）： in: current node, score if current node is score node if current node is left leaf return count of right sibling else # current node is right node, no right sibling return 0 else # current node is score range node if score in left subtree…
-
zero sum subsequence problem solution 1
题目是这样的，给定一个整数序列，比如[1, 2, -1, 8, -9]，要求找出一个子序列，其所有数字的和为0，比如子序列[2, -1, 8, -9]，并输出子序列在主序列中的位置，比如[2, -1, 8, 9]在主序列[1, 2, -1, 8, -9]中的位置为[1, 4]。 以下是我想到的一个方法，暂时不清楚怎么计算这个的时间复杂度。原理是这样的，对于序列[1, 2, -1, 8, -9]，设置一个和序列。初始为[0, 0, 0, 0, 0]，长度和输入序列一致。 顺序读取输入序列，第一次遇到1，尝试在和序列的[0, 0]区别内增加1，结果为[1, 0, 0, 0, 0]。为什么这么做呢，这样，输入序列区间[0, 0]的和就计算出来了。 第二次遇到2， 尝试在和序列[0, 1]区间内增加2，结果为[3, 2, 0, 0, 0]，这样，输入序列区间[0, 1], [1, 1]的和就计算出来了。没有发现0和序列。 接下来依此类推，发现[1, 4]区间的和为0，输出为（1， 4）。代码如下（python）： #!/usr/bin/env python import sys def find_zero_sum_seq(seq): sums = [0] *…