4. 最长连续数列

2020-09-04

XMOJ

hash

4 分钟读完 (大约 594 个字) 0次访问

XMOJ 4. 最长连续数列

题目：4. 最长连续数列

描述:

输入一个乱序的连续数列，输出其中最长连续数列长度，要求算法复杂度为 O(n)

输入:

54,55,300,12,56

输出:

你的输出是对一行数据处理的结果，也即 a+b 的结果。

输入样例:

100,4,200,1,3,2
54,55,300,12
1
5,4,3,2,1
1,2,3,4,5,6

输出样例:

4
2
1
5
6

方法：hash

思路：hash表，将输入数字依次加入hash表中，然后依次根据输入数字去删除hash表中的数字，以及相邻数字的，记录删除的数字的个数，数字个数即为该输入数字所在连续数列的长度，之后继续通过上述方法获取每一个输入数据所在连续序列的长度，其中最长的连续序列长度，即为整个乱序的连续数列的最长连续数列长度。

运行数据：最大执行时间：106.15 ms，内存消耗：17344 KiB

复杂度分析：

由于输入数据组数无法确定，时间复杂度和空间复杂度只考虑一组数据。

时间复杂度：O(n)，n为一组输入数据的个数，加入hash表的时间复杂度为O(n)，删除hash表中所有数字的时间复杂度也为O(n)。
空间复杂度：O(n)，n为一组输入数据的个数，主要为保存拆分字符串的字符串数组的空间消耗以及hash表的空间消耗。

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        String line;
        while (scan.hasNextLine()) {
            line = scan.nextLine().trim();
            System.out.println(LongestContinuousSequence(line));
        }
    }

    private static int LongestContinuousSequence(String line) {

        String[] strs = line.split(",");
        Set<Integer> set = new HashSet<>();

        for (String string : strs) {
            set.add(Integer.valueOf(string));
        }

        int ans = 0;

        for (String string : strs) {

            int count = 0;
            int i = Integer.valueOf(string);
            int j = i + 1;

            // 删除输入数字及其相邻数字，统计该输入数字所在的连续序列长度
            while (set.remove(i)) {
                count++;
                i--;
            }

            while (set.remove(j)) {
                count++;
                j++;
            }

            ans = Math.max(ans, count);
        }

        return ans;
    }
}