Java算法题-解析最长连续序列问题

题目

在这个算法题中，我们将解决如何找出给定未排序整数数组中的最长连续序列的问题。最长连续序列是指在该序列中，元素间的差值为1。

引言

找出未排序整数数组中的最长连续序列需要一种有效的方法来追踪数组中的元素，以及快速检查某个元素是否在数组中。通常，使用哈希集合（HashSet）可以帮助我们解决这个问题。

算法思路

1. 首先，将数组中的所有元素放入一个哈希集合中，这可以用来快速检查某个元素是否在数组中。
2. 然后，对数组中的每个元素进行遍历，对于每个元素，都尝试向两边扩展，查找连续序列的长度。为了避免重复计算，只对每个连续序列的起始元素进行扩展。
3. 在扩展时，我们可以通过不断地检查元素是否在哈希集合中来判断是否可以继续扩展，直到不再能够扩展为止。同时，我们可以记录当前连续序列的长度，并不断更新最长连续序列的长度。

代码实现

以下是使用 Java 实现的解决方案：

javaCopy codeimport java.util.HashSet;
import java.util.Set;

public class LongestConsecutiveSequence {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int longestStreak = 0;

        for (int num : numSet) {
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (numSet.contains(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}

算法分析

• 时间复杂度：遍历数组一次，对于每个元素，最多进行两次连续序列的扩展，因此时间复杂度为 O(N)，其中 N 是数组的长度。
• 空间复杂度：使用了额外的哈希集合来存储数组中的元素，空间复杂度为 O(N)。

示例和测试

我们可以使用以下代码进行测试：

public class Main {
    public static void main(String[] args) {
        LongestConsecutiveSequence solution = new LongestConsecutiveSequence();
        int[] nums = {100, 4, 200, 1, 3, 2};

        int longestStreak = solution.longestConsecutive(nums);
        System.out.println("最长连续序列的长度: " + longestStreak); // 输出 4
    }
}

总结

找出未排序整数数组中的最长连续序列需要使用哈希集合来追踪元素和快速检查元素是否在数组中。通过遍历数组并不断扩展连续序列，我们可以高效地解决这个问题。这个问题的时间复杂度是 O(N)，空间复杂度是 O(N)，其中 N 是数组的长度。理解哈希集合的使用对于解决类似的问题非常有帮助。