leetcode-128

发表于 | 更新于: | 分类于 |
字数统计: 1.2k 字

最近在复习贪心算法，复习到了并查集这个数据结构，因此写一道用并查集来解决的算法题。

题目

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

1
2
3
4
> Input: [100, 4, 200, 1, 3, 2]
> Output: 4
> Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
>

分析

这道题让我们求出一个无序数组中最长的连续序列的长度，难度在于时间复杂度要求在O(n)内，用并查集可以达到这个要求。

首先来复习一下并查集这个数据结构。

并查集

并查集是一种树型数据结构，用于处理一些不相交集合的合并及查询问题，用它来判断元素所在集合所用时间接近常数级，Kruskal最小生成树算法就用到了并查集来实现。

假设有一个动态集合S={s1，s2，s3，…..sn}，每个子集合通过一个代表来标识，代表就是这个子集合中的一个元素，即根元素。要判断两个元素是否属于同一个子集合，判断它们的根元素是否是同一个代表即可。

随着union操作，子集合的个数会越来越少，因此称之为动态集合。

并查集主要涉及3种基本操作：

  1. makeset：初始化，每个元素作为一个子集合，它的父节点是本身，集合树高度为1
  2. find(x)：找出某个元素x的根元素，所需时间与树的高度成正比。在优化的并查集中，经常在find(x)过程中把根节点更新为x的父节点，这样可以降低树的高度，在总体上提高find和union的效率，这个优化被称为路径压缩
  3. union(x，y)：合并包含x和y的集合，一般是让较低的树的根指向较高的树的根。只有当两棵树高度相同时，合并后总高度才增加。

解法

在本题中，连续的序列可以视为一个集合，集合中的元素值是连续的，而我们要做的事情就是找到最大的集合大小。

使用并查集，我们可以在O(n)时间内完成任务，因为经过优化后的find操作耗时接近常数级。

本题，我们可以遍历一次数组，假设当前遍历到的元素值为x，查询x+1和x-1是否在数组中，如果在，就合并它们所在的子集合，最终找出最大子集合的大小。

通过使用hash map，我们可以解决三个问题：

  • 把在数组中操作的问题转成在并查集中操作，键值对作为数组元素与并查集元素之间的联系
  • 并查集中不能有两个重复的元素，否则结果会偏大
  • 查询x+1和x-1是否在数组中的操作耗时O(1)

另外需要注意，在这个问题的并查集中使用级别来合并子集合并不适用，要换成根节点所具有的孩子数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <vector>
#include <unordered_map>
using std::cout;
using std::vector;
using std::unordered_map;

class UnionFindSet {
private:
    int size;
    vector<int> parent;
    //child表示根节点的孩子数
    vector<int> child;
public:
    UnionFindSet(int size) {
        this->size = size;
        parent = vector<int>(size);
        child = vector<int>(size);
    }

    void makeSet() {
        for (int i = 0; i < size; ++i) {
            parent[i] = i;
            child[i] = 1;
        }
    }

    int find(int x) {
        //查找过程中使用路径压缩
        if (x != parent[x]) parent[x] = find(parent[x]);
        return parent[x];
    }

    void Union(int x, int y) {
        int parent_x = find(x);
        int parent_y = find(y);
        if (parent_x == parent_y) return;
        if (child[parent_x] > child[parent_y]) {
            parent[parent_y] = parent_x;
            child[parent_x] += child[parent_y];
        }
        else {
            parent[parent_x] = parent_y;
            child[parent_y] += child[parent_x];
        }
    }

    int max_child() {
        int max = 1;
        for (auto i : child) {
            if (max < i) max = i;
        }
        return max;
    }
};

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        //利用hashmap来记录元素是否存在
        //键为元素值，值为元素在并查集中的位置
        unordered_map<int, int> map;
        for (int i = 0; i < nums.size(); ++i) {
            map.insert(std::make_pair(nums[i], i));
        }
        UnionFindSet set(nums.size());
        set.makeSet();
        for (auto it = map.begin(); it != map.end(); ++it) {
            auto smaller = map.find(it->first - 1);
            auto bigger = map.find(it->first + 1);
            //比元素小1的元素存在
            if (smaller != map.end()) {
                set.Union(it->second, map[it->first - 1]);
            }
            //比元素小1的元素存在
            if (bigger != map.end()) {
                set.Union(it->second, map[it->first + 1]);
            }
        }
        return set.max_child();
    }
};
-------------本文结束感谢您的阅读-------------