本文详细介绍了如何在Java中高效地查找一个混合了数字和特定标记(如”I”)的数组中最长连续数字序列的长度。通过迭代遍历数组,利用两个变量动态跟踪当前连续数字序列长度和迄今为止的最大长度,该方法能够简洁、鲁棒地处理各种输入情况,包括全数字、全标记或混合序列,并提供了清晰的代码示例和详细解析。
问题描述与挑战
在实际编程中,我们经常会遇到需要从结构化数据中提取特定模式的需求。本教程关注的是一个具体场景:给定一个数组,其中每个元素要么是一个表示“未完成”的特定标记(例如字符串”i”),要么是一个表示“已完成”的数字。我们的目标是找出数组中最长的连续数字序列的长度。
示例: 假设输入数组为 [4, 15, 9, “I”, 30, 2, “I”, 20]。
- 4, 15, 9 构成一个长度为3的连续数字序列。
- 30, 2 构成一个长度为2的连续数字序列。
- 20 构成一个长度为1的连续数字序列。 根据定义,最长的连续数字序列是 [4, 15, 9],其长度为3。
解决此问题的挑战在于:
- 需要识别数组中的数字和非数字标记。
- 当遇到非数字标记时,需要正确地中断当前序列的计数。
- 要能够准确地记录并更新迄今为止找到的最长序列长度,无论该序列出现在数组的哪个位置。
- 代码应能鲁棒地处理各种边界情况,例如数组只包含数字、只包含标记”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 } }
代码详解
-
变量初始化:
- int res = 0;:res 用于存储算法执行过程中发现的最长连续数字序列的长度。它初始化为0,因为在没有任何数字序列的情况下,最长长度就是0。
- int cur = 0;:cur 用于存储当前正在计数的连续数字序列的长度。每次遇到数字时,它会递增;当遇到非数字标记时,它会重置为0。
-
遍历数组:
立即学习“Java免费学习笔记(深入)”;
- for (int i = 0; i
-
核心逻辑判断:
- 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。这表示当前的数字序列仍在继续。
- cur = “I”.equals(items[i]) ? 0 : cur + 1;
-
更新最长序列:
- res = Math.max(res, cur);:在每次更新 cur 的值之后,我们都将其与 res 进行比较,并将两者中的较大值赋给 res。这确保了 res 始终保持着迄今为止遇到的最长连续数字序列的长度。即使 cur 重置为0,res 也不会受到影响,因为它只记录最大值。
-
返回结果:
- return res;:循环结束后,res 中存储的就是整个数组中最长连续数字序列的长度。
示例与运行
为了更好地理解算法的执行过程,我们以示例数组 Object[] items = {4, 15, 9, “I”, 30, 2, “I”, 20}; 为例,逐步跟踪 cur 和 res 的值变化。
步骤 (i) | items[i] | items[i].equals(“I”) | cur (更新后) | res (更新后) | 说明 |
---|---|---|---|---|---|
初始值 | 0 | 0 | |||
0 | 4 | false | 0 + 1 = 1 | max(0, 1) = 1 | 遇到数字,cur 增加 |
1 | 15 | false | 1 + 1 = 2 | max(1, 2) = 2 | 遇到数字,cur 增加 |
2 | 9 | false | 2 + 1 = 3 | max(2, 3) = 3 | 遇到数字,cur 增加,此时 res 达到最大 |
3 | “I” | true | 0 | max(3, 0) = 3 | 遇到”I”,cur 重置为0,res 不变 |
4 | 30 | false | 0 + 1 = 1 | max(3, 1) = 3 | 遇到数字,cur 增加 |
5 | 2 | false | 1 + 1 = 2 | max(3, 2) = 3 | 遇到数字,cur 增加 |
6 | “I” | true | 0 | max(3, 0) = 3 | 遇到”I”,cur 重置为0,res 不变 |
7 | 20 | false | 0 + 1 = 1 | max(3, 1) = 3 | 遇到数字,cur 增加 |
最终,循环结束,方法返回 res 的值,即 3,这与预期结果一致。
注意事项与扩展
-
输入类型考量:
- 本教程提供的解决方案假设输入数组 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; // }
-
时间复杂度:
- 该算法仅对数组进行了一次遍历,每次迭代的操作都是常数时间(比较、加法、最大值计算)。因此,其时间复杂度为 O(N),其中 N 是数组中元素的数量。这是一种非常高效的解决方案。
-
空间复杂度:
- 算法只使用了几个固定的变量(res, cur, i),不随输入数组的大小而变化。因此,其空间复杂度为 O(1),即常数空间。
-
**
© 版权声明
文章版权归作者所有,未经允许请勿转载。
THE END