Boyer-Moore多数表决算法

问题陈述

假设你有一个未排序的值列表。你想知道列表中是否存在该列表中一半以上元素的值。如果有则这个值是什么?尽可能高效地完成此任务。

出现此问题的一个常见原因可能是容错计算。执行多个冗余计算,然后验证大多数结果是否一致。‘

简单的解决方案

简单的解决方案是哈希表。时间复杂度是O(N),空间复杂度是O(N)。

Boyer-Moore多数表决算法

首先检查该count值。如果计数等于0,则将设置candidate为当前元素的值。接下来,首先将元素的值与当前candidate值进行比较。如果它们相同,则增加count1。如果它们不同,则减少count1。

candidate = 0
count = 0
for value in input:
  if count == 0:
    candidate = value
  if candidate == value:
    count += 1
  else:
    count -= 1

最终 candidate 即为众数,该算法空间复杂度是O(1)。

我们用下面一组数据来理解,我们把 5 看成 -1 ;0 看成 +1 ,只要不同就相互抵消,相同的元素相加,多的一方一定会把另一方抵消掉。下面是计算过程:

[5, 5, 0, 0, 0, 5, 0, 0, 5]

[1, 2, 1, 0, 1, 0, 1, 2, 1]  // count 取值

[5, 5, 5, 5, 0, 0, 0, 0, 0]  // candidate 取值

推广

每次删除三个不相同的数,最后留下的可能是出现次数超过1/3的数,这个思想可以推广到出现次数超过1/k次的元素有哪些。需要注意的是最后还需要再遍历一遍结果,判断次数最多和次多的是不是超过了⌊ n/3 ⌋次。

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int m = 0, n = 0, cm = 0, cn = 0;
        for (int i : nums) {
            if (m == i) {
                ++cm;
            } else if (n == i) {
                ++cn;
            } else if (cm == 0) {
                m = i;
                cm = 1;
            } else if (cn == 0) {
                n = i;
                cn = 1;
            } else {
                --cm;
                --cn;
            }
        }
        cm = cn = 0;
        for (int i : nums) {
            if (i == m)
                ++cm;
            else if (i == n)
                ++cn;
        }
        vector<int> res;
        const int N = nums.size();
        if (cm > N / 3)
            res.push_back(m);
        if (cn > N / 3)
            res.push_back(n);
        return res;
    }
};

并行计算

Finding the Majority Element in Parallel

以 [1, 1, 1, 2, 1, 2, 1, 2, 2] 为例,我们可以将其拆开。

分组1:
[1, 1, 1, 2, 1]
candidate = 1
count = 3

分组2:
[2, 1, 2, 2]
candidate = 2
count = 2

可以将第1部分的结果视为与[1,1,1]相同,而将第2部分的结果视为与[2,2]。

参考文章:

https://gregable.com/2013/10/majority-vote-algorithm-find-majority.html

一种使用倒排索引和位图的快速SKU选择方法

使用所有有货的SKU组合生成该SKU到该组合的索引。如 [A-B,B-C] 即生成 {A:[1],B:[1,2],C:[2]}
映射到视图时只需要判断当前选中项的SKU索引的交集(默认为全集),例如选中B,则[1,2,3][1,2]的交集[1,2],然后依次遍历SKU,判断SKU对应的索引与当前选中索引是否有交集。如果有则可选,没有则置灰。

索引可以使用位图数据结构,在判断是否为交集使用位运算提升性能。

   const sku = [];
    const revertIndex = {};
    const size = 8;
    // 随机sku
    for (let i = 0; i < size; i++) {
        sku[i] = new Set();
        for (let j = 0; j < size; j++) {
            const v = j * size + RandomNumBoth(0, size);
            sku[i].add(v)
        }
    }

    for (let i = 0; i < sku.length; i++) {
        sku[i].forEach((e) => {
            if (!revertIndex[e]) revertIndex[e] = 0;
            revertIndex[e] |= 1 << i
        })
    }

判断是否选中使用 (revertIndex[(line-1)*size + e -1] & union)

下面是一个简单的例子,取消选择和选中逻辑是一样的,所以就暂时没写:

See the Pen SKU Demo by zhangchen (@zhangchen915) on CodePen.

不相交集合元素的数据结构——并查集

不相交集合有两种基本操作:合并(union)和查询(find)。

并查集保持了一组不相交的动态集合,每个集合通过一个代表来识别,代表即集合中的某个成员。

数组实现Quick Find

我们可以直接用数组来存储集合的标识,这样查找操作直接返回对应数组的值即可,复杂度为O(1);而合并操作每次都需要遍历整个数组,复杂度为O(n)

     0   1   2   3   4   5   6   7   8   9
     -------------------------------------
 id  0   1   2   3   4   5   6   7   8   9

union(1, 4)
union(1, 5)

     0   1   2   3   4   5   6   7   8   9
     -------------------------------------
 id  0   1   2   3   1   1   6   7   8   9

有根树表示 Quick Union

为了降低合并操作的复杂度,我们可以用多个有根树表示集合,每个结点存储指向其父亲结点的指针,根节点指向自己。判断是否属于同一个集合时,我们只需要判断元素所属的树根是否相同。

批注 2019-10-08 010040.jpg

这种方式实际上并没有本质提高,而且如果一些极端情况下会退化成一个链表,查找操作的复杂度反而上升了,上面的例子中就是这样。

查找和合并的时间复杂度都为O(h),h表示树高。

所以我们需要对合并操作进行优化,优化方式一般为以下两种。

按秩合并(union by rank)

秩(Rank)就是一颗树的结点数,即使包含较少结点的树根指向包含较多结点的树根。
所以上面的例子中union(1, 2)操作会让 2 节点会指向 1 。
批注 2019-10-08 010145.jpg

这样查找操作最坏情况的时间复杂度为O(logN)

路径压缩

在查找所在位置是我们会进行递归,那么我们可以利用递归回溯的过程进行路径压缩。所谓压缩表示的就是将从x结点搜索到祖先结点所经过的结点都指向该树的根节点结点。
DSU_path_compression.png

在压缩之后树的高度低了,所以查找复杂度也降低了。

同时使用按秩合并和路径压缩

复杂度为反阿克曼函数,具体的证明比较复杂,可以参科下面这篇讲义。
这里简单介绍下阿克曼函数,他表示f(n) = 2 ^2^2^…^2,可见其增长速度极快,其反函数用lg*n表示,其值可以认为小于5。

https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/UnionFind.pdf

批注 2019-10-08 010145.jpg
参考文章:
https://cp-algorithms.com/data_structures/disjoint_set_union.html
https://algs4.cs.princeton.edu/15uf/

子元素 diff 算法的优化

5a58d2b2bbd4b-min.jpg

React 的 Diff

React先遍历新数组来找到插入和需要移动的节点,为了避免不必要的移动,react使用了一个哨兵值lastIndex,记录访问过的源数组下标最大值,如果当前元素的下标小于lastIndex,表示原相对位置无法满足需要了需要移动,否则更新lastIndex,这样来最大限度地利用原相对位置。
最后遍历一遍旧数组找到需要删除的元素。

但这种方式并不是总能得到最优结果。

例如:'1234' ➔ '4123'
React 并没有将4移到最前面,而是将234都移动一次。因为对新数组的遍历是从左向右的依次进行,所以这种位置相对关系总是局部的。

Diff 的改进

缩小问题规模

首先考虑一种情况,我们只对字符串进行了一次插入或删除操作,其实是没有必要进行diff,我们通过匹配两个字符串的通用前缀/后缀,可以直接找出差异,即便字符串进行了多次插入删除,查找公共前后缀也能在一定程度上减小diff的计算量,因为使用二分搜索的时间复杂度是O(nlogn)。

例如下面的两个字符串的公共前缀为abc,后缀为g,可以直接去掉。

A: -> [a b c d e f g] <-
B: -> [a b c h f e g] <-

寻找最小的移动次数

diff 算法首先需要一个旧数组的索引{1:0,2:1,3:2,4:3},通过该索引计算出新数组的对应位置。然后计算数组索引的最长上升子序列,通常使用动态规划实现,具体不做展开。

A: [a b c d]
B: [d a b c]
P: [3 0 1 2]
LIS: [0 1 2]

然后我们自右向左遍历新数组和 LIS 序列,查看元素的位置是否能与 LIS 序列的任何一个值匹配,若匹配则位置无需移动,然后取前一个LIS值继续,否则将其移动到当前遍历新数组元素的前面。
如上面的例子中,中有遍历到第一位时才不匹配,所以将B[1]=d移动到A[1]=a的前面即可。

为什么LIS能够做到这一点,因为它在整体上保留了数组升序排列的相对位置。

参考文章:
https://www.zhihu.com/question/65824137
https://github.com/NervJS/nerv/issues/3

比较排序与计数排序时间复杂度的证明

比较排序

对于任意的比较排序算法,我们都能将其操作抽象成一颗决策树,这是一颗完全二叉树,它表示了某一排序算法对所有元素的比较操作。下图是插入排序的例子:
批注 2019-09-04 010631.jpg

每一条路径都是一种可能性,所以算法的最坏情况下的排序次数就是决策树的高度。

n个元素,可能的排序结果有A(n,n-1)=n!种,假设此时的树高为h,则叶子节点最多为2^(h+1)

2^(h+1) ≥ n!  
h + 1 ≥ log2(n!)

log(n!) = O(nlogn)

证明:

不等式缩放

log(n!) = log1 + ... + logn ≥ n/2 * log(n/2) = n/2 * logn - n/2 = c1 * logn
log(n!) = log1 + ... + logn ≤ nlogn = c2 * logn

Stirling 近似

76029ac06006a23f29011873c13a7a64541c6acd.svg

a35e8e0205988cf8552eec558d121f764d7e4021.svg

计数排序

计数排序的思想是:在待排序序列中,如果我们能统计出有多少元素小于或等于某一个元素,我们也就知道了该元素的正确位置。
例如:有五个元素小于x,那么就把x放到第六位(对于相同的元素我们认为最早遇到小于后面遇到的)。

实现该算法我们需要三个数组,初始input,结果output和表示元素统计数的count数组。
下面为算法的伪代码:

count = array of k+1 zeros
for x in input:
   count[key(x)] += 1

total = 0
for i in 0, 1, ... k:
   count[i], total = total, count[i] + total

output = array of the same length as input
for x in input:
   output[count[key(x)]] = x
   count[key(x)] += 1

return output

算法可视化

时间复杂度分析:假设在[0,k]的n个元素,数组初始化O(k),构造统计数组C是O(n),统计数累加O(k),排序是O(n)
所以总共时间复杂度为O(k+n)

计数排序是一种典型空间换时间的算法。

性能比较

下面是JS中的性能对比:

Array with 10000000 elements:
n log(n) takes 15.611 seconds
Linear takes 3.896 seconds

参考文章:
https://medium.com/free-code-camp/my-favorite-linear-time-sorting-algorithm-f82f88b5daa1