Algorithm

从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存有一个元素（或者说，有个权值）。 堆性质：父亲的权值不小于儿子的权值（大根堆）。同样的，我们可以定义小根堆。本文以大根堆为例。 ...

计算数组中所有数在数轴上两两之间的距离的和 例如：[1,2,4,9]，结果为 (2-1)+(4-1)+(9-1)+(4-2)+(9-2)+(9-4)=26； 思路：从小到大枚举 $nums[i]$，此时左边有 $i$ 个数字，右边有 $n-i$ 个数字（算上 $nums[i]$），所以共有 $i\times (n−i)$ 对数字在计算距离时会累加 $nums[i] - nums[i-1]$。我们依次遍历完 $[1,n-1]$ 范围内所有的 $nums[i]$，将 $(nums[i] - nums[i - 1]) * i * (n - i)$ 累加到答案中即可。 ...

快速幂，二进制取幂（Binary Exponentiation，也称平方法），是一个在 $O(\log n)$ 的时间内计算 $a^n$ 的小技巧，而暴力的计算需要 $O(n)$ 的时间。 过程 首先将 $n$ 表示为二进制，例如 ...

逆元 逆元通常是用来解决除法求模问题的，求模运算有以下法则： $$ \begin{cases} (a+b)\%c&=&(a\%c+b\%c)\%c\quad &加法法则\\[1ex] (a-b)\%c&=&(a\%c-b\%c)\%c\quad &减法法则\\[1ex] (a*b)\%c&=&(a\%c*b\%c)\%c\quad &乘法法则 \end{cases} $$可以发现，除法求模没有相应的法则。当计算 $\cfrac{a}{b}\%c$ 时，如果 $a$，$b$ 很大，不能在计算完之后取模，可以通过变换将除法变为乘法，然后就可以通过上面的公式取模了。 ...

TopK 问题指的是寻找数组第 $K$ 大/小的元素。一种简单的做法是对数组排序，然后取第 $K$ 个元素，时间复杂度为 $O(NlogN)$，接下来以寻找第 $K$ 大的元素为例，介绍另外两种做法。 ...