Java对象数组最长连续数字序列查找方法

问题描述与挑战

在实际编程中，我们经常会遇到需要从结构化数据中提取特定模式的需求。本教程关注的是一个具体场景：给定一个数组，其中每个元素要么是一个表示“未完成”的特定标记（例如字符串"I"），要么是一个表示“已完成”的数字。我们的目标是找出数组中最长的连续数字序列的长度。

示例： 假设输入数组为 [4, 15, 9, "I", 30, 2, "I", 20]。

• 4, 15, 9 构成一个长度为3的连续数字序列。
• 30, 2 构成一个长度为2的连续数字序列。
• 20 构成一个长度为1的连续数字序列。 根据定义，最长的连续数字序列是 [4, 15, 9]，其长度为3。

解决此问题的挑战在于：

1. 需要识别数组中的数字和非数字标记。
2. 当遇到非数字标记时，需要正确地中断当前序列的计数。
3. 要能够准确地记录并更新迄今为止找到的最长序列长度，无论该序列出现在数组的哪个位置。
4. 代码应能鲁棒地处理各种边界情况，例如数组只包含数字、只包含标记"I"或为空数组。

核心算法解析

为了高效地解决这个问题，我们可以采用一种简洁的单次遍历算法。该算法的核心思想是维护两个变量：一个用于跟踪当前连续数字序列的长度，另一个用于记录迄今为止发现的最长连续数字序列的长度。

public class LongestConsecutiveSequence {

    /**
     * 查找对象数组中最长连续数字序列的长度。
     * 数组元素可以是表示数字的Integer对象，或表示中断的字符串"I"。
     *
     * @param items 包含数字（Integer）或标记（"I"）的Object数组。
     * @return 最长连续数字序列的长度。
     */
    public static int findLongestConsecutiveNumberSequenceLength(Object[] items) {
        int res = 0; // 存储迄今为止找到的最长连续序列长度
        int cur = 0; // 存储当前正在计数的连续序列长度

        // 遍历数组中的每一个元素
        for (int i = 0; i < items.length; i++) {
            // 判断当前元素是否为字符串"I"
            // 如果是"I"，表示数字序列中断，当前序列长度重置为0
            // 如果不是"I"（例如，它是一个Integer对象），则表示当前元素是数字，当前序列长度加1
            // 这种比较方式对于Object[]数组中包含String "I"和Integer对象的情况是有效的，
            // 因为Integer对象的equals()方法与String "I"比较会返回false。
            cur = "I".equals(items[i]) ? 0 : cur + 1;

            // 每次更新cur后，都将其与res（最长序列长度）进行比较，
            // 确保res始终保持迄今为止的最大值
            res = Math.max(res, cur);
        }

        // 循环结束后，res即为所求的最长连续数字序列长度
        return res;
    }

    public static void main(String[] args) {
        // 示例数组1：混合类型
        Object[] example1 = {4, 15, 9, "I", 30, 2, "I", 20};
        System.out.println("Example 1: " + findLongestConsecutiveNumberSequenceLength(example1)); // Output: 3

        // 示例数组2：全数字
        Object[] example2 = {1, 2, 3, 4, 5};
        System.out.println("Example 2: " + findLongestConsecutiveNumberSequenceLength(example2)); // Output: 5

        // 示例数组3：全"I"
        Object[] example3 = {"I", "I", "I"};
        System.out.println("Example 3: " + findLongestConsecutiveNumberSequenceLength(example3)); // Output: 0

        // 示例数组4：空数组
        Object[] example4 = {};
        System.out.println("Example 4: " + findLongestConsecutiveNumberSequenceLength(example4)); // Output: 0

        // 示例数组5：开头和结尾是"I"
        Object[] example5 = {"I", 10, 20, "I", 30, 40, 50, "I"};
        System.out.println("Example 5: " + findLongestConsecutiveNumberSequenceLength(example5)); // Output: 3
    }
}

代码详解

1. 变量初始化：

   • int res = 0;：res 用于存储算法执行过程中发现的最长连续数字序列的长度。它初始化为0，因为在没有任何数字序列的情况下，最长长度就是0。
   • int cur = 0;：cur 用于存储当前正在计数的连续数字序列的长度。每次遇到数字时，它会递增；当遇到非数字标记时，它会重置为0。

2. 遍历数组：

   • for (int i = 0; i < items.length; i++)：通过一个简单的 for 循环遍历输入数组 items 中的每一个元素。

3. 核心逻辑判断：

   • cur = "I".equals(items[i]) ? 0 : cur + 1;
     • 这是算法最关键的一行。它使用三元运算符来根据当前元素的值更新 cur。
     • "I".equals(items[i])：这个条件判断当前元素 items[i] 是否等于字符串 "I"。
       • 重要说明： 这里的 items 是 Object[] 类型。如果 items[i] 是一个 String 对象（例如 new String("I") 或 String 字面量 "I"），equals() 方法会正确比较其内容。如果 items[i] 是一个 Integer 对象（例如 Integer.valueOf(4)），那么 Integer 对象的 equals() 方法与 String "I" 比较时，会返回 false（因为它们的类型不同），从而正确地将 Integer 对象识别为“非'I'”，并进入 cur + 1 的逻辑。这使得该方法对于 String "I" 和 Integer 对象的混合数组具有良好的鲁棒性。
     • 如果条件为真（即 items[i] 是 "I"），则 cur 被重置为 0。这意味着当前的连续数字序列被中断。
     • 如果条件为假（即 items[i] 不是 "I"，而是数字），则 cur 递增 1。这表示当前的数字序列仍在继续。

4. 更新最长序列：

   • res = Math.max(res, cur);：在每次更新 cur 的值之后，我们都将其与 res 进行比较，并将两者中的较大值赋给 res。这确保了 res 始终保持着迄今为止遇到的最长连续数字序列的长度。即使 cur 重置为0，res 也不会受到影响，因为它只记录最大值。

5. 返回结果：

   • return res;：循环结束后，res 中存储的就是整个数组中最长连续数字序列的长度。

示例与运行

为了更好地理解算法的执行过程，我们以示例数组 Object[] items = {4, 15, 9, "I", 30, 2, "I", 20}; 为例，逐步跟踪 cur 和 res 的值变化。

最终，循环结束，方法返回 res 的值，即 3，这与预期结果一致。

注意事项与扩展

1. 输入类型考量：

   • 本教程提供的解决方案假设输入数组 Object[] items 中，数字以 Integer 对象的类型存在，而标记为 String "I"。在这种情况下，"I".equals(items[i]) 能够正确区分数字和标记。
   • 如果输入数组是 String[] 且数字也以字符串形式存在（例如 {"4", "15", "9", "I"}），则需要额外的解析逻辑来判断一个字符串是否代表数字。例如，可以使用 try-catch 结构尝试 Integer.parseInt(items[i])，或者利用 Character.isDigit() 检查字符串的第一个字符（如果数字总是正整数）。

     // 示例：如果输入是 String[] 且数字为字符串
     // public static int findLongestConsecutiveNumberSequenceLength(String[] items) {
     //     int res = 0;
     //     int cur = 0;
     //     for (String item : items) {
     //         try {
     //             Integer.parseInt(item); // 尝试解析为数字
     //             cur++;
     //         } catch (NumberFormatException e) {
     //             // 解析失败，或者当前字符串就是"I"
     //             cur = 0;
     //         }
     //         res = Math.max(res, cur);
     //     }
     //     return res;
     // }

2. 时间复杂度：

   • 该算法仅对数组进行了一次遍历，每次迭代的操作都是常数时间（比较、加法、最大值计算）。因此，其时间复杂度为 O(N)，其中 N 是数组中元素的数量。这是一种非常高效的解决方案。

3. 空间复杂度：

   • 算法只使用了几个固定的变量（res, cur, i），不随输入数组的大小而变化。因此，其空间复杂度为 O(1)，即常数空间。

4. **