跳到主要内容

最长连续序列

· 阅读需 8 分钟
Eureka X
Eureka X
Mr.Nobody

力扣面试经典——128题​

💡 参考代码：​

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

// 哈希表节点结构
typedef struct HashNode {
    int key;
    int value;  // 用于标记是否已访问
    UT_hash_handle hh;  // uthash所需句柄
} HashNode;

/**
 * 寻找最长连续序列长度
 * @param nums 整数数组
 * @param numsSize 数组长度
 * @return 最长连续序列的长度
 */
int longestConsecutive(int* nums, int numsSize) {
    // 边界条件处理：空数组直接返回0
    if (numsSize == 0) {
        return 0;
    }

    HashNode* hashTable = NULL;  // 初始化哈希表
    HashNode* tmp;
    
    // 第一步：将所有元素存入哈希表，去重并建立快速查找结构
    for (int i = 0; i < numsSize; i++) {
        // 查找当前元素是否已存在于哈希表中
        HASH_FIND_INT(hashTable, &nums[i], tmp);
        if (tmp == NULL) {
            // 若不存在，则创建新节点并插入哈希表
            tmp = (HashNode*)malloc(sizeof(HashNode));
            tmp->key = nums[i];
            tmp->value = 0;  // 0表示未访问过
            HASH_ADD_INT(hashTable, key, tmp);
        }
    }
    
    int maxLength = 0;  // 记录最长连续序列长度
    
    // 遍历哈希表中的每个元素
    HashNode* current;
    HashNode* tmpIter;
    HASH_ITER(hh, hashTable, current, tmpIter) {
        // 只有当current->key-1不存在时，current->key才是某个连续序列的起点
        HASH_FIND_INT(hashTable, &(current->key - 1), tmp);
        if (tmp == NULL) {
            // 找到序列起点，从该点开始向后查找连续元素
            int currentNum = current->key;
            int currentLength = 1;
            
            // 向后查找连续元素
            HASH_FIND_INT(hashTable, &(currentNum + 1), tmp);
            while (tmp != NULL) {
                tmp->value = 1;  // 标记为已访问
                currentLength++;
                currentNum++;
                HASH_FIND_INT(hashTable, &(currentNum + 1), tmp);
            }
            
            // 更新最大长度
            if (currentLength > maxLength) {
                maxLength = currentLength;
            }
        }
    }
    
    // 清理哈希表内存
    HashNode* el;
    HashNode* tmpEl;
    HASH_ITER(hh, hashTable, el, tmpEl) {
        HASH_DEL(hashTable, el);
        free(el);
    }
    
    return maxLength;
}

// 测试函数
int main() {
    // 测试用例1
    int nums1[] = {100, 4, 200, 1, 3, 2};
    int size1 = sizeof(nums1)/sizeof(nums1[0]);
    printf("Test 1: %d\n", longestConsecutive(nums1, size1));  // 预期输出: 4
    
    // 测试用例2
    int nums2[] = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
    int size2 = sizeof(nums2)/sizeof(nums2[0]);
    printf("Test 2: %d\n", longestConsecutive(nums2, size2));  // 预期输出: 9
    
    // 测试用例3
    int nums3[] = {1, 0, 1, 2};
    int size3 = sizeof(nums3)/sizeof(nums3[0]);
    printf("Test 3: %d\n", longestConsecutive(nums3, size3));  // 预期输出: 3
    
    return 0;
}

📖 总结：​

点击展开题目总结

🤔 最长连续序列

1️⃣ 题目核心信息​

🎯 功能描述：给定一个未排序的整数数组，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

📥 输入输出：

  • 输入：
    • nums: 整数数组，包含待处理的数字序列
    • numsSize: 数组长度，表示数组中元素的个数
  • 输出：返回最长连续数字序列的长度

2️⃣ 实现原理​

💡 核心思路：使用哈希表存储所有数字，然后只从连续序列的起点开始计数，避免重复计算。

📋 实现步骤：

  1. 遍历数组，将所有元素存入哈希表实现去重和快速查找
  2. 再次遍历哈希表中的元素，判断每个元素是否为连续序列的起点
  3. 对于每个起点，向后查找连续元素并计算序列长度
  4. 记录并更新最长序列长度

3️⃣ 关键点解析​

🎯 代码技巧​

  • 使用UTHASH库实现哈希表功能，提供O(1)的查找效率
  • 通过检查n-1是否存在来确定n是否为序列起点，避免重复计算
  • 只对序列起点进行扩展搜索，确保每个元素最多被访问两次
  • 使用HASH_ITER安全地遍历和删除哈希表元素

4️⃣ 使用场景​

✅ 适用情况：​

  • 需要在一个未排序数组中查找最长连续数字序列
  • 数据范围较大，不能使用排序算法
  • 需要O(n)时间复杂度的解决方案

⚠️ 前提条件：​

  • 数组元素为整数
  • 可以使用额外的O(n)空间
  • 允许修改哈希表中的元素状态

5️⃣ 复杂度分析​

  • ⏱️ 时间复杂度：O(n) - 每个元素最多被访问两次
  • 💾 空间复杂度：O(n) - 需要哈希表存储所有元素

6️⃣ 注意事项​

🚩 边界情况：​

  • 空数组：直接返回0
  • 单个元素数组：返回1
  • 包含重复元素：哈希表自动去重处理

💥 易错点：​

  • 不能对表达式取地址（如&(current->key - 1)），需要先计算值再取地址
  • 忘记释放哈希表内存导致内存泄漏
  • 没有正确判断序列起点导致重复计算

7️⃣ 补充说明​

以数组 [100, 4, 200, 1, 3, 2]为例：

步骤1：构建哈希表​

首先将数组中所有元素存入哈希表：

哈希表内容：{100, 4, 200, 1, 3, 2}

步骤2：遍历哈希表寻找序列起点​

遍历哈希表中的每个元素，判断是否为序列起点：

  1. 检查元素100：

    • 判断99是否存在 → 不存在
    • 所以100是序列起点
    • 从100开始向后查找：100 → 无后续元素
    • 序列长度：1

  2. 检查元素4：

    • 判断3是否存在 → 存在
    • 所以4不是序列起点，跳过

  3. 检查元素200：

    • 判断199是否存在 → 不存在
    • 所以200是序列起点
    • 从200开始向后查找：200 → 无后续元素
    • 序列长度：1

  4. 检查元素1：

    • 判断0是否存在 → 不存在
    • 所以1是序列起点
    • 从1开始向后查找：
      • 1 → 存在2
      • 2 → 存在3
      • 3 → 存在4
      • 4 → 无后续元素
    • 序列长度：4 ([1,2,3,4])

  5. 检查元素3：

    • 判断2是否存在 → 存在
    • 所以3不是序列起点，跳过

  6. 检查元素2：

    • 判断1是否存在 → 存在
    • 所以2不是序列起点，跳过

步骤3：得出结果​

比较所有序列长度，最长的序列是[1,2,3,4]，长度为4。

算法优化点​

  1. 避免重复计算：只从序列起点开始查找，避免了对[2,3,4]、[3,4]等子序列的重复计算
  2. 高效查找：使用哈希表实现O(1)时间复杂度的元素查找
  3. 线性时间复杂度：虽然有嵌套循环，但每个元素最多被访问两次，总体时间复杂度为O(n)

通过这种方式，算法能够在线性时间内找出最长连续序列，而不需要先对数组进行排序。

加载评论中...