题解 | #连续的牛群标签序列#【Java】

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param tag int整型一维数组
     * @return int整型
     */
    public int longestConsecutive(int[] tag) {
        HashSet<Integer> hashSet = new HashSet<>();
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < tag.length; i++) {
            if(tag[i]<min){
                min = tag[i];
            }
            hashSet.add(tag[i]);
        }
        int length = 1;
        int max = Integer.MIN_VALUE;
        Iterator<Integer> iterator = hashSet.iterator();
        while(iterator.hasNext()){
           Integer next = iterator.next();
           while(true){
               if(hashSet.contains(next+1)){
                   length++;
                   next++;
               }else{
                   break;
               }
           }
            max = Math.max(max,length);
           length = 1;
       }
       return max;
    }
}

本题知识点分析：

1.哈希表的存取

2.数组遍历

3.API取最大值(Math.max)

4.迭代器遍历

本题解题思路分析：

1.先将所有数字放入hashSet有重复的直接去重，因为求的连续最长序列，重复数字没有用

2.迭代器遍历hashSet,每次取出的数字，然后去判断是否有next++，也就是连续递增的数字

3.记录每个数字连续递增的最大长度，然后用max函数比较，取最大长度

4.最后返回最大长度即可

5.题解的时间复杂度是O（n）,别看两个while(true)就是O(n2)，HashSet的contains方法可以在常数时间内判断元素是否存在。

本题使用编程语言: Java

题目明确不能使用排序，并且要时间复杂度O（n）,我都不知道有些人做题是为了什么？搁着面试的时候，不按面试官要求来？

如果本篇文章对您有帮助的话，可以点个赞支持一下，感谢~