给定一个未排序的整数数组 nums
,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
请你设计并实现时间复杂度为 O(n)
的算法解决此问题。
- int cmp(const void* a,const void* b){
- return *(int*)a - *(int*)b;
- }
- int longestConsecutive(int* nums, int numsSize){
- if(numsSize == 0)
- return 0;
- qsort(nums,numsSize,sizeof(int),cmp);
- int max = 1,sum = 1;
- for(int i = 1;i < numsSize;i++){
- if(nums[i] == nums[i - 1] + 1)
- sum++;
- else if(nums[i] == nums[i - 1])
- continue;
- else
- sum = 1;
- max = max > sum ? max : sum;
- }
- return max;
- }
- #define HASH_BASE (10031)
-
- int hash_index(int a)
- {
- int t;
-
- t = a % HASH_BASE;
- if (t < 0) {
- t = HASH_BASE + t;
- }
- return t;
- }
-
- int longestConsecutive(int* nums, int numsSize){
- int i, cnt, lmax, cur;
- bool *hs;
-
- hs = malloc(sizeof(bool) * (HASH_BASE));
- memset(hs, 0, sizeof(bool) * (HASH_BASE));
-
- for (i = 0; i < numsSize; i++) {
- hs[hash_index(nums[i])] = true;
- }
-
- lmax = 0;
- for (i = 0; i < numsSize; i++) {
- if (!hs[hash_index(nums[i] - 1)]) {
- cnt = 1;
- cur = nums[i];
- while (hs[hash_index(cur + 1)]) {
- cnt++;
- cur++;
- }
- if (cnt > lmax) {
- lmax = cnt;
- }
- }
- }
- free(hs);
- return lmax;
- }
本题要求最长连续序列,可以将先将数组内数先排序一遍,再向后不断遍历数组比较得到最长连续序列,但时间复杂度不合要求,可以想到若先将数组内数放置在哈希表中再查找时间复杂度仅为O(n),所以将数存到哈希表中,利用find找到最长连续序列,最后输出即可
本题考察哈希表的应用,将值存入哈希表中再查找可达到O(n)的时间复杂度