每日一题——最长连续序列和uthash.h

LeetCode128. 最长连续序列（C语言实现）

问题描述

给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例

1. 输入：nums = [100, 4, 200, 1, 3, 2]
   输出：4
   解释：最长数字连续序列是 [1, 2, 3, 4]，其长度为 4。

2. 输入：nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
   输出：9
   解释：最长数字连续序列是 [0, 1, 2, 3, 4, 5, 6, 7, 8]，其长度为 9。

3. 输入：nums = [1, 0, 1, 2]
   输出：3
   解释：最长数字连续序列是 [0, 1, 2]，其长度为 3。

约束条件

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

解题思路

为了在 O(n) 时间复杂度内解决此问题，我们需要利用哈希表来快速查找元素是否存在。具体步骤如下：

1. 构建哈希表：将数组中的所有元素插入到哈希表中，确保每个元素唯一。
2. 遍历哈希表：对于每个元素，检查它是否是某个连续序列的起点（即检查 x-1 是否存在）。
3. 查找连续序列：如果当前元素是序列的起点，则从该元素开始，逐个查找后续元素，直到找不到为止。
4. 更新最大长度：记录每次找到的连续序列长度，并更新最长序列的长度。

C语言实现代码

以下是完整的C语言实现代码，使用了 uthash 库来实现哈希表功能。

#include <stdio.h>
#include <stdlib.h>
#include <uthash.h>

// 定义哈希表结构体
typedef struct {
    int key; // 哈希集合保存的元素
    UT_hash_handle hh; // uthash 需要
} hashTable;

// 函数：找出数字连续的最长序列长度
int longestConsecutive(int* nums, int numsSize) {
    hashTable* hashMap = NULL; // 创建一个空哈希集合
    hashTable* hashNode;

    // 构建哈希集合
    for (int i = 0; i < numsSize; i++) {
        int key = nums[i];
        HASH_FIND_INT(hashMap, &key, hashNode);
        if (hashNode == NULL) { // 如果 nums[i] 不在集合中，则插入
            hashNode = (hashTable*)malloc(sizeof(hashTable));
            hashNode->key = key;
            HASH_ADD_INT(hashMap, key, hashNode);
        }
    }

    int result = 0; // 初始化最大长度为0
    hashTable* current, *next; // 用于遍历哈希表的指针

    // 遍历哈希表中的每个节点
    HASH_ITER(hh, hashMap, current, next) {
        int x = current->key; // 当前节点的值
        hashTable* prevNode; // 用于检查前驱节点是否存在
        int prevKey = x - 1; // 前驱节点的键为 x-1
        HASH_FIND_INT(hashMap, &prevKey, prevNode);

        // 如果前驱节点存在，则跳过当前节点，因为当前节点不是序列的起点
        if (prevNode != NULL) {
            continue;
        }

        // 否则，当前节点是序列的起点，开始查找最长连续序列
        int end = x; // 连续序列的终点初始化为起点
        hashTable* temp; // 用于查找后继节点
        // 不断查找下一个节点，直到找不到时停止
        do {
            end++; // 假设下一个节点存在
            HASH_FIND_INT(hashMap, &end, temp); // 检查下一个节点是否存在
        } while (temp != NULL); // 如果存在，则继续查找

        // 计算当前连续序列的长度
        int currentLength = end - x;
        // 更新最大长度
        if (currentLength > result) {
            result = currentLength;
        }
    }

    // 清空哈希表，释放内存
    HASH_CLEAR(hh, hashMap);

    return result; // 返回最长连续序列的长度
}

代码说明

1. 构建哈希表：

   • 使用 uthash 库构建哈希表，将数组中的每个元素插入到哈希表中，确保每个元素唯一。

2. 遍历哈希表：

   • 遍历哈希表中的每个节点，检查当前节点是否为某个连续序列的起点。通过判断 x-1 是否存在，确定当前节点是否为序列的起点。

3. 查找连续序列：

   • 对于每个序列的起点，从该节点开始，逐个查找后续节点，直到找不到为止。

4. 更新最大长度：

   • 每次找到一个连续序列后，计算其长度，并更新最长序列的长度。

5. 时间复杂度：

   • 构建哈希表的时间复杂度为 O(n)。
   • 遍历哈希表的时间复杂度为 O(n)，每个元素最多被处理两次（一次在遍历时，一次在查找连续序列时）。
   • 因此，总时间复杂度为 O(n)。

测试结果

1. 输入：nums = [100, 4, 200, 1, 3, 2]
   输出：4
   解释：最长连续序列是 [1, 2, 3, 4]。

2. 输入：nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
   输出：9
   解释：最长连续序列是 [0, 1, 2, 3, 4, 5, 6, 7, 8]。

3. 输入：nums = [1, 0, 1, 2]
   输出：3
   解释：最长连续序列是 [0, 1, 2]。

uthash.h

uthash 是一个轻量级的哈希表库，广泛用于 C 语言中。以下是 uthash 的一些常用函数及其用法：

1. HASH_ADD_INT

用于向哈希表中添加一个整数键的节点。

HASH_ADD_INT(哈希表指针, 键字段名, 节点指针);

• 哈希表指针：指向哈希表的指针。
• 键字段名：结构体中存储键值的字段名。
• 节点指针：指向要插入的节点的指针。

2. HASH_FIND_INT

在哈希表中查找一个整数键的节点。

HASH_FIND_INT(哈希表指针, 键值地址, 节点指针);

• 哈希表指针：指向哈希表的指针。
• 键值地址：键值的地址（通常用 & 取地址）。
• 节点指针：用于存储查找结果的指针。

3. HASH_ITER

用于遍历哈希表中的所有节点。

HASH_ITER(UT_hash_handle字段名, 哈希表指针, 当前节点指针, 下一个节点指针);

• UT_hash_handle字段名：结构体中 UT_hash_handle 类型字段的名称。
• 哈希表指针：指向哈希表的指针。
• 当前节点指针：用于存储当前节点的指针。
• 下一个节点指针：用于存储下一个节点的指针。

4. HASH_DEL

从哈希表中删除一个节点。

HASH_DEL(哈希表指针, 节点指针);

• 哈希表指针：指向哈希表的指针。
• 节点指针：指向要删除的节点的指针。

5. HASH_COUNT

获取哈希表中节点的数量。

int count = HASH_COUNT(哈希表指针);

• 哈希表指针：指向哈希表的指针。
• 返回值：哈希表中节点的数量。

6. HASH_CLEAR

清空哈希表中的所有节点。

HASH_CLEAR(UT_hash_handle字段名, 哈希表指针);

• UT_hash_handle字段名：结构体中 UT_hash_handle 类型字段的名称。
• 哈希表指针：指向哈希表的指针。

总结

关键在于：

1. 利用哈希表快速查找元素是否存在。
2. 通过判断 x-1 是否存在，避免重复计算连续序列。
3. 逐个查找后续节点，直到找不到为止。
   另外，要学会uthash.h使用，这才是最难的，不过多刷几题也就熟悉了。