Skip to content

Latest commit

 

History

History
290 lines (203 loc) · 6.41 KB

基础提升02.md

File metadata and controls

290 lines (203 loc) · 6.41 KB
Raw

2. 并查集与有序表

MyUnionFindSet.cpp

2.1 岛问题

【题目】

一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右 四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛？

【举例】

001010

111010

100100

000000

这个矩阵中有三个岛

  • 时间复杂度：O(N*M)
int countIslands(vector<vector<int>>& m){
    if(m.size() < 1 || m[0].size() < 1){
        return 0;
    }
    int N = m.size();
    int M = m[0].size();
    int res = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(m[i][j] == 1){
                res++;
                infect(m, i, j, N, M);
            }
        }
    }
}
void infect(vector<vector<int>>& m, int i, int j, int N, int M){
    if(i < 0 || i >= N || j < 0 || j > M || m[i][j] != 1){
        return;
    }
    m[i][j] = 2;
    infect(m, i + 1, j, N, M);
    infect(m, i - 1, j, N, M);
    infect(m, i, j + 1, N, M);
    infect(m, i, j - 1, N, M);
}

【进阶】

如何设计一个并行算法解决这个问题 (google)

并查集

2.2 并查集

N个样本，当 findHead 的调用次数逼近O(N)及以上时，单次 findHead 的调用代价为：O(1)

template <typename V>
class Element {
public:
    Element(V v) : value(v) {}
    V value;
};

template <typename V>
class UnionFindSet {
public:
    UnionFindSet(list<V> l) {
        for (auto value : l) {
            Element* element = new Element(value);
            elementMap.insert(pair<V, Element*>(value, element));
            fatherMap.insert(pair<Element*, Element*>(element, element));
            sizeMap.insert(pair<Element*, V>(element, 1));
        }
    }

    // 给定一个ele，往上一直找，把代表元素返回
    Element<V>* findHead(Element<V>* element) {
        stack<Element*> path;
        while (element != fatherMap.at(element)) {
            path.push(element);
            element = fatherMap.at(element);
        }
        // 扁平化处理
        while (!path.empty()) {
            fatherMap.insert(pair<Element*, Element*>(path.top(), element));
            path.pop();
        }
        return element;
    }

    bool isSameSet(int a, int b) {
        if (elementMap.find(a) != elementMap.end() && elementMap.find(b) != elementMap.end()) {
            return findHead(elementMap.at(a)) == findHead(elementMap.at(b));
        }
        return false;
    }

    void unionSet(int a, int b) {
        if (elementMap.find(a) != elementMap.end() && elementMap.find(b) != elementMap.end()) {
            Element* aF = findHead(elementMap.at(a));
            Element* bF = findHead(elementMap.at(b));
            if (aF != bF) {
                Element* big = sizeMap.at(aF) >= sizeMap.at(bF) ? aF : bF;
                Element* small = big == aF ? bF : aF;
                fatherMap.insert(pair<Element<V>*, Element<V>*>(small, big));
                sizeMap.insert(pair<Element<V>*, V>(big, sizeMap.at(aF) + sizeMap.at(bF)));
                sizeMap.erase(small);
            }
        }
    }

    // 样本对应的元素
    unordered_map<V, Element<V>*> elementMap;
    // key: 某个元素，value: 该元素的父
    unordered_map<Element<V>*, Element<V>*> fatherMap;
    // key: 某个集合的代表元素，value: 该集合的大小
    unordered_map<Element<V>*, V> sizeMap;
};

2.3 有序表

  • 支持哈希表的所有操作

  • key 是有序组织的

  • 小于等于某个数最近的key，大于等于某个数最近的 key

  • 所有操作都是 O(logN) 级别的

2.3.1 可以实现有序表的结构

平衡搜索二叉树(BST)系列

  • 红黑树

  • AVL树（高度平衡树）

  • SB树 （Size Balanced Tree）比赛常用

单链表系列

  • 跳表 （SkipList）

2.3.2 搜索二叉树

  1. 从头节点出发，小的往左滑，大的往右滑

  2. 默认搜索二叉树无重复值（有重复值时进行压缩）

  3. 无平衡性，时间复杂度无法维持在 O(logN) 的水平

平衡性：

  • 狭义平衡性：平衡搜索二叉树，严格的左右两棵树的高度差不超过1

  • 广义平衡性：左树和右树的体量差不多大

2.3.3 左旋和右旋

带有自平衡操作的搜索二叉树 = 搜索二叉树 + 左旋右旋操作

  • AVL = (搜索二叉树 + 左旋右旋操作) + 怎么用左旋，右旋

  • 红黑树 = (搜索二叉树 + 左旋右旋操作) + 怎么用左旋，右旋

  • SB树 = (搜索二叉树 + 左旋右旋操作) + 怎么用左旋，右旋

左旋：头节点往左边倒

右旋：头节点往右边倒

通过左旋右旋操作，可以让树变平衡一点

2.3.4 AVL树

平衡标准：严格的左右两棵树的高度差不超过1

1. 检查时机

  • 从加入节点开始往上，检查所有节点是否有平衡性

  • 从删除节点往上，检查所有节点是否有平衡性

    • 左右子树都存在时，从替换节点的原上一节点开始进行平衡性检查

2. 破坏平衡性的四种类型

LL型：左孩子的左边过长

  • 单次右旋

RR型：右孩子的右边过长

  • 单次左旋

LR型

  • 先左旋，后右旋

RL型

  • 先右旋，后左旋
// todo

2.3.5 SB树(Size Balanced Tree)

判断平衡性的条件（平衡标准）不一样

平衡标准：

  • 每棵子树的大小，不小于其兄弟的子树大小
  • 既每棵叔叔树的大小，不小于其任何侄子树的大小

LL 型：节点 T 的左孩子的左孩子的大小，大于节点 T 的右孩子的大小

m(T){
    - 右旋
    - m(T)
    - m(L)
}

LR型：

m(T){
    - 左旋
    - 右旋
    - m(T)
    - m(L)
    - m(B)
}
// todo

2.3.6 红黑树

平衡标准：

  1. 每个节点不是红就是黑

  2. 任何两个红节点不能相邻

  3. 整棵树的头节点和底层的叶节点（最底层的空节点）必须为黑

  4. cur出发，到叶节点的每一条路，要求黑节点数量一样

最长的路和最短的路不会超过两倍以上。

2.3.7 跳表

随机思想

// 待整理
class SkipListNode{
public:
    int key;
    int val;
    list<SkipListNode*> nextNodes;

    SkipListNode(int k, int v) : key(k), val(v) { }

    bool isKeyLess(int otherKey){
        return otherKey != NULL && (key == NULL || key < otherKey); 
    }

    bool isKeyEqual(int otherKey){
        return (key == NULL && otherKey == NULL) 
            || (key != NULL && otherKey != null && key == otherKey);
    }
};