找到最长的连续数字序列

问题H（最长的自然inheritance者）：

如果第二个整数是自然数序列中第一个的inheritance者，则两个连续的整数是自然后继的（1和2是自然后继者）。 编写一个读取数字N后跟N个整数的程序，然后打印连续自然后继的最长序列的长度。

例：

输入7 2 3 5 6 7 9 10输出3这是我的代码到目前为止，我不知道为什么它不起作用

import java.util.Scanner; public class Conse { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int x = scan.nextInt(); int[] array = new int[x]; for (int i = 0; i < array.length; i++) { array[i] = scan.nextInt(); } System.out.println(array(array)); } public static int array(int[] array) { int count = 0, temp = 0; for (int i = 0; i < array.length; i++) { count = 0; for (int j = i, k = i + 1; j < array.length - 1; j++, k++) { if (Math.abs(array[j] - array[k]) == 1) { count++; } else { if (temp <= count) { temp = count; } break; } } } return temp + 1; } } 

Answer 1

为什么两个循环？ 关于什么

 public static int array(final int[] array) { int lastNo = -100; int maxConsecutiveNumbers = 0; int currentConsecutiveNumbers = 0; for (int i = 0; i < array.length; i++) { if (array[i] == lastNo + 1) { currentConsecutiveNumbers++; maxConsecutiveNumbers = Math.max(maxConsecutiveNumbers, currentConsecutiveNumbers); } else { currentConsecutiveNumbers = 1; } lastNo = array[i]; } return Math.max(maxConsecutiveNumbers, currentConsecutiveNumbers); } 

Answer 2

这似乎有效：

 public static int longestConsecutive(int[] array) { int longest = 0; // For each possible start for (int i = 0; i < array.length; i++) { // Count consecutive. for (int j = i + 1; j < array.length; j++) { // This one consecutive to last? if (Math.abs(array[j] - array[j - 1]) == 1) { // Is it longer? if (j - i > longest) { // Yup! Remember it. longest = j - i; } } else { // Start again. break; } } } return longest + 1; } public void test() { int[] a = new int[]{7, 2, 3, 5, 6, 7, 9, 10}; System.out.println("Longest: " + Arrays.toString(a) + "=" + longestConsecutive(a)); } 

版画

 Longest: [7, 2, 3, 5, 6, 7, 9, 10]=3 

Answer 3

由于您的问题与“问题H”有关，我假设您只是在学习。 更简单总是更好，因此通过编写接近问题的代码“ 如何完成”，通常需要将其分解为“必须完成的工作”才能开始特定的道路。

在这种情况下，您可能会使数组过于复杂。 如果数字大于前一个数字，则数字是自然inheritance者。 如果是，则增加当前序列的计数。 如果没有，我们将开始一个新的序列。 如果当前序列长度大于我们看到的最大序列长度，则将最大序列长度设置为当前序列长度。 不需要数组 – 您只需要比较两个数字（当前和最后读取的数字）。

例如：

 public static void main(String[] args) { Scanner scan = new Scanner(System.in); int N = scan.nextInt(); int maxSequenceLen = 0; // longest sequence ever int curSequenceLen = 0; // when starting new sequence, reset to 1 (count the reset #) int last = 0; for(int i = 0; i < N; i++) { int cur = scan.nextInt(); if ((last+1) == cur){ ++curSequenceLen; } else{ curSequenceLen = 1; } if (curSequenceLen > maxSequenceLen){ maxSequenceLen = curSequenceLen; } last = cur; } System.out.println(maxSequenceLen); 

警告：我在没有Java开发环境的计算机上回答这个问题，因此代码未经测试。

Answer 4

我不确定我是否理解这个问题。 这里写的答案假设自然inheritance者连续发生。 但如果这不相同，那么这里的解决方案可能无法给出正确的答案。

假设输入是[7 2 6 3 7 5 6 9 10]而不是[7 2 3 5 6 7 9 10] ，则答案变为2而arrays中存在自然后继[5 6 7] 。

如果输入没有排序，我们将不得不使用不同的方法。 就像使用HashSet一样

1. 将整个数组加载到HashSet ，以删除重复项。
2. 从HashSet选择第一个值并将其指定为start和end ，并将其从集合中删除。
3. 现在减量start并检查它是否存在于HashSet并继续直到HashSet中不存在特定的start值，同时从集合中删除正在搜索的值。
4. 为end做同样的事情，除了你必须为每次迭代增加end的值。
5. 我们现在必须在集合中从start到end连续范围，其范围是current_Max = end - start + 1
6. 在每次迭代中，我们跟踪此current_Max以获得整个arrays的最长自然后继。

由于HashSet支持在O(1)时间内添加，删除，更新。 该算法将在O(n)时间内运行，其中n是输入数组的长度。 可以在此处找到C＃中此方法的代码