leetcode之最长连续子序列

大学生每天刷leetcode要坚持下去是怎么回事呢?大学生相信大家都很熟悉,但是大学生每天刷leetcode要坚持下去是怎么回事呢,下面就让小编带大家一起了解吧。大学生每天刷leetcode要坚持下去,其实就是刷力扣对提高思维能力很有帮助,大家可能会很惊讶大学生怎么会每天刷leetcode要坚持下去呢?但事实就是这样,小编也感到非常惊讶。

今天小编会带来一条什么题目呢??现在就给大家揭晓题目如下~~

先审题~~

发现这个题目其实很好理解~~题如其名,就是要在乱序的数组里找到最长连续子序列~~~

这题虽然被标注为HARD,但是小编完全不再怕的~~ hard的原因是题目中要求复杂度必须要在O(n)以内,小编现在和大家一起扩展思路~

假如没有复杂度的限制,而仅仅如题目中所说只要找出最长连续子序列,该怎么做呢???

思路一:

暴力解法:对每个数都寻找他接下来的连续的数,然后再一起比较谁最长,这样子的复杂度是O(n^3),显然是太复杂了~~~

思路二:

排序法:先将数组排序再进行子序列长度的度量,选择最长的。酱紫排序的复杂度为O(lgn),总体的复杂度就是O(nlgn),看起来还好~~但是还有很多提升空间,一定要加油哦!!排序法的C代码如下:

#include

int compare(const void* a, const void* b)

{

return *((unsigned int*)a) - *((unsigned int*)b);

}

//以上这个compare函数主要是为了C语言里面的qsort函数啦~~具体想了解这个qsort函数的函数的话呢,小编这里建议百度啦~~~这里面的a,b都采用了(unsigned int*)主要是为了表达位数比int更加多~~~

int longestConsecutive(int* num, int numSize)

{

  while(numSize != 0 ){   

//这是要判断数组是不是[ ]也就是里面什么都没有~~,区别于[0]哦!

qsort(num, numSize, sizeof(int), compare);

//这个函数就是C语言里面的 qsort啦!

int max = 0, temp = 1;

for(int i = 1; i

{

  if(num[i] == num[i-1])  continue;//一样的值就不管他,跳出本次for循环但是temp的值依然记录着~~

  if(num[i] == num[i-1]+1)

    temp++;

 else

  {

    max = (max> temp)?max:temp;

    temp = 1;//一旦途中的连续值断了,这里必须要重置temp的值哦!!!!

  }

}

return (max> temp)?max:temp;//最终输出~~

}

return 0;//数组是[ ]的话,输出是0哦~~~

}

好了,以上就是排序法的所有代码了!!小编也非常开心,因为排序法非常好理解,但是复杂度还不够要求,接下来小编就带来本题的最终解法!!

思路三:

哈希表~~哈希表和线性空间的构造(其实可以被看作是思路一暴力法的优化啦!!)

HashMap中的key表示读到的数组中每个元素的值,value对应的是数组中每个key所处的连续序列的长度!

遍历数组nums[i]的时候将数组中每一个元素插入到HashMap去,可能出现以下几种情况:

(1)插入HashMap中该元素已经被插入过,则不插入。

(2)插入HashMap中该元素没有被插入过且该元素没有相邻的元素,则令key=nums[i],value=1,插入到HashMap中去即可。

(3)插入HashMap中某元素key=3时,有比它大的相邻的元素,则一直遍历找到与它相邻序列中最大的那个元素,然后将连续序列的首尾key对应的value更新为连续序列的长度。

key      3    4    5

value   3     2    3

(4)插入HashMap中某元素key=7时,有比它小的且相邻的元素,则一直遍历HashMap找到与它相邻序列中最小的那个元素,然后将连续序列首尾的Key对应的value更新为最新的连续序列的长度个数。

key      5    6    7

value   3     2    3

(5)插入HashMap中某元素key=5时,有比它大的相邻的元素,也有比它小的相邻的元素的时候,我们先遍历HashMap找到与它相邻且比它大的序列中最大的那个元素,然后将连续序列的首尾key对应的value更新为最新的连续序列的长度;然后遍历HashMap找到与它相邻且比它小的序列中最小的那个元素,然后将最长的连续序列的首尾的Key对应的value更新为序列的长度。

key      3   4    5    6    7

value   5    2    3    2    5

以上就是哈希表的构造方法了!是不是很神奇呢!!!小编也很惊讶于程序员的智慧!!!

接下来就是代码实现了~~~~~~

struct mystruct{

  int number;

  UT_hash_handle hh;

};

struct mystruct *t;

struct mystruct *find(int number) {

  struct mystruct *s;

  HASH_FIND_INT(t, &number, s);

  return s;

}//定义了结构体相关,小编这里不想展开写了,有问题评论区见吧~~~

void add(int num){

  struct mystruct *s = (struct mystruct *)malloc(sizeof(struct mystruct));

  if(find(num) == NULL){//没被插入的key就存入~

      s->number = num;

      HASH_ADD_INT(t, number, s); 

  } 

}

int longestConsecutive(int* nums, int numSize){

  t = NULL;

  int max = 0;

  if(numSize == 0)

      return numSize;

  for(int i = 0; i < numSize; i++){

      add(nums[i]);

  }

  for(int i = 0; i < numSize; i++){

      if(find(nums[i] + 1) == NULL){

          int tmp, n;//tmp用来保存比该元素大的且连续的最大的那个元素

          n = nums[i];

          tmp = n;

          while(find(n)){

              n -= 1;

          }                                           

          max = ((tmp - n) > max) ? (tmp - n) : max;

      }

  }   

  return max;

}

好了~~小编写到这里就已经很困啦~~

先晚安啦~~~

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20200606A0PXV300?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券