1.本题不难理解如果不考虑时间复杂度为O(n)的要求直接将原数组排序后遍历即可但这样的时间复杂度为O(nlogn)不满足要求这也是这题的难点所在。2.已知本题一定需要使用哈希表时间复杂度为O(n)的要求即为遍历常数遍数组就能得出答案思考之后想到解法如下1创建visited[100001]数组元素全部初始化为0它的核心作用有两个一是在构建哈希表时对原数组的相同元素去重二是在后续探索序列时充当剪枝标记防止重复遍历。2使用C语言的uthash库先遍历一遍完整数组当遍历到的数组的值为第一次遇到时创建节点同时初始化节点的节点号idx i、保存的长度段len 1最少就是只有自身长度为1。如果不是第一次则将visited数组中该下标的元素值1然后跳过该元素以实现去重。3设置一个while循环开始再次遍历完整数组。当遇到visited数组中该下标的元素值不为0时直接跳过。每次都寻找当前值1的节点如果有则将初始节点中的cur-len next-len。这样做可以保证每次都只将连续序列片段的长度保存到片段的头节点之后搜寻到之前的节点可以直接加上这段片段的长度从而避免重复扫描。4总结这样做不仅把连续序列的长度不断累加保存到了片段的“头节点”上而且如果在探索过程中接轨了以前探索过的旧片段可以直接把整段旧长度“吸收”过来。配合visited数组标记彻底避免了任何一个元素的重复扫描完美实现了的时间复杂度O(n)。3.基于以上思想写出的完整代码如下1. typedef struct{ 2. int key; 3. int idx; 4. int len; 5. UT_hash_handle hh; 6. } HashEntry; 7. 8. int longestConsecutive(int* nums, int numsSize) { 9. // 数组为空时不存在连续序列直接返回0 10. if (numsSize 0) return 0; 11. 12. // visited数组标记nums中下标i的元素是否重复/已处理大小固定100001 13. int visited[100001] {0}; 14. // uthash哈希表头用于存放所有不重复的数字 15. HashEntry* hashTable NULL; 16. // 第一次遍历数组完成去重并构建哈希表 17. for (int i 0; i numsSize; i){ 18. HashEntry* entry; 19. // 在哈希表中查找当前数字nums[i] 20. HASH_FIND_INT(hashTable, nums[i], entry); 21. // 当前数字未存入哈希表新建节点插入 22. if (entry NULL){ 23. entry (HashEntry*)malloc(sizeof(HashEntry)); 24. entry-key nums[i]; // 存储数字本身 25. entry-idx i; // 记录该数字第一次出现的下标 26. entry-len 1; // 初始连续序列长度为1 27. HASH_ADD_INT(hashTable, key, entry); 28. } else { 29. // 数字重复标记当前下标已跳过后续不再处理 30. visited[i]; 31. } 32. } 33. 34. // 全局最长连续序列长度最少为1单个数字 35. int res 1; 36. // 第二次遍历数组所有下标 37. for (int i 0; i numsSize; i){ 38. // 当前下标是重复数字已标记跳过直接进入下一轮 39. if (visited[i] ! 0) continue; 40. 41. HashEntry* cur; 42. HashEntry* next; 43. // 获取当前数字对应的哈希节点 44. HASH_FIND_INT(hashTable, nums[i], cur); 45. // 查找当前数字的下一个连续数字 46. int find nums[i] 1; 47. HASH_FIND_INT(hashTable, find, next); 48. // 存在后继数字且该数字未被处理循环向后扩展连续序列 49. while (next ! NULL visited[next-idx] 0){ 50. // 标记该后继数字下标已处理防止重复计算 51. visited[next-idx]; 52. // 累加连续序列长度 53. cur-len next-len; 54. // 更新全局最大长度 55. res fmax(cur-len, res); 56. // 继续查找下一位连续数字 57. find; 58. HASH_FIND_INT(hashTable, find, next); 59. } 60. } 61. 62. return res; 63. }该算法的时间复杂度和空间复杂度均为O(n)已是最优解。4.以下是ai总结的算法逻辑 刷题笔记:力扣第128题-最长连续序列
1.本题不难理解如果不考虑时间复杂度为O(n)的要求直接将原数组排序后遍历即可但这样的时间复杂度为O(nlogn)不满足要求这也是这题的难点所在。2.已知本题一定需要使用哈希表时间复杂度为O(n)的要求即为遍历常数遍数组就能得出答案思考之后想到解法如下1创建visited[100001]数组元素全部初始化为0它的核心作用有两个一是在构建哈希表时对原数组的相同元素去重二是在后续探索序列时充当剪枝标记防止重复遍历。2使用C语言的uthash库先遍历一遍完整数组当遍历到的数组的值为第一次遇到时创建节点同时初始化节点的节点号idx i、保存的长度段len 1最少就是只有自身长度为1。如果不是第一次则将visited数组中该下标的元素值1然后跳过该元素以实现去重。3设置一个while循环开始再次遍历完整数组。当遇到visited数组中该下标的元素值不为0时直接跳过。每次都寻找当前值1的节点如果有则将初始节点中的cur-len next-len。这样做可以保证每次都只将连续序列片段的长度保存到片段的头节点之后搜寻到之前的节点可以直接加上这段片段的长度从而避免重复扫描。4总结这样做不仅把连续序列的长度不断累加保存到了片段的“头节点”上而且如果在探索过程中接轨了以前探索过的旧片段可以直接把整段旧长度“吸收”过来。配合visited数组标记彻底避免了任何一个元素的重复扫描完美实现了的时间复杂度O(n)。3.基于以上思想写出的完整代码如下1. typedef struct{ 2. int key; 3. int idx; 4. int len; 5. UT_hash_handle hh; 6. } HashEntry; 7. 8. int longestConsecutive(int* nums, int numsSize) { 9. // 数组为空时不存在连续序列直接返回0 10. if (numsSize 0) return 0; 11. 12. // visited数组标记nums中下标i的元素是否重复/已处理大小固定100001 13. int visited[100001] {0}; 14. // uthash哈希表头用于存放所有不重复的数字 15. HashEntry* hashTable NULL; 16. // 第一次遍历数组完成去重并构建哈希表 17. for (int i 0; i numsSize; i){ 18. HashEntry* entry; 19. // 在哈希表中查找当前数字nums[i] 20. HASH_FIND_INT(hashTable, nums[i], entry); 21. // 当前数字未存入哈希表新建节点插入 22. if (entry NULL){ 23. entry (HashEntry*)malloc(sizeof(HashEntry)); 24. entry-key nums[i]; // 存储数字本身 25. entry-idx i; // 记录该数字第一次出现的下标 26. entry-len 1; // 初始连续序列长度为1 27. HASH_ADD_INT(hashTable, key, entry); 28. } else { 29. // 数字重复标记当前下标已跳过后续不再处理 30. visited[i]; 31. } 32. } 33. 34. // 全局最长连续序列长度最少为1单个数字 35. int res 1; 36. // 第二次遍历数组所有下标 37. for (int i 0; i numsSize; i){ 38. // 当前下标是重复数字已标记跳过直接进入下一轮 39. if (visited[i] ! 0) continue; 40. 41. HashEntry* cur; 42. HashEntry* next; 43. // 获取当前数字对应的哈希节点 44. HASH_FIND_INT(hashTable, nums[i], cur); 45. // 查找当前数字的下一个连续数字 46. int find nums[i] 1; 47. HASH_FIND_INT(hashTable, find, next); 48. // 存在后继数字且该数字未被处理循环向后扩展连续序列 49. while (next ! NULL visited[next-idx] 0){ 50. // 标记该后继数字下标已处理防止重复计算 51. visited[next-idx]; 52. // 累加连续序列长度 53. cur-len next-len; 54. // 更新全局最大长度 55. res fmax(cur-len, res); 56. // 继续查找下一位连续数字 57. find; 58. HASH_FIND_INT(hashTable, find, next); 59. } 60. } 61. 62. return res; 63. }该算法的时间复杂度和空间复杂度均为O(n)已是最优解。4.以下是ai总结的算法逻辑