找到的連續編號的最長序列

Question

問題H（最長自然後繼）：

兩個連續的整數是天然的後繼如果第二是第一的自然數的序列（1和2是天然的後繼）在後繼。編寫一個程序，讀取一個數字N，後跟N個整數，然後打印出最長連續自然後繼序列的長度。

例子：

輸入7 2 3 5 6 7 8 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」 與之相關聯的，我假設你剛開始學習。簡單總是更好，所以在開始某條特定道路之前，通常需要將它分解成「什麼必須完成」，然後通過編寫接近「」這樣的問題的代碼來完成。「

在這種情況下，您可能會使數組過於複雜化。如果一個數字大於前一個數字，那麼它就是一個自然的繼承者。如果這是真的，則遞增當前序列的計數。如果不是，我們開始一個新的序列。如果當前序列長度大於我們所看到的最大序列長度，請將最大序列長度設置爲當前序列長度。不需要數組 - 你只需要比較兩個數字（當前和最後一個數字）。

例如：

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

我不確定我是否正確理解了這個問題。這裏寫的答案假定自然繼承者是連續發生的。但是，如果這不相同，那麼這裏的解決方案可能不會給出正確的答案。

假設代替[7 2 3 5 6 7 9 10]輸入是[7 2 6 3 7 5 6 9 10]那麼答案變成2，而陣列中存在自然後繼[5 6 7]。

如果輸入未排序，我們將不得不使用不同的方法。像使用HashSet

1. 將整個陣列加載到一個HashSet刪除重複項。
2. 從HashSet中選取第一個值，並將其分配給start和end，並將其從集中移除。
3. 現在遞減start並檢查它是否存在於HashSet中並繼續，直到start的特定值不存在爲止HashSet刪除正在搜索的值。
4. 對end做同樣的事情，除了你將不得不增加每個迭代的值end。
5. 我們現在有連續的範圍從start到end存在於集，其範圍爲current_Max = end - start + 1
6. 在每次迭代中，我們跟蹤這個current_Max的在整個陣列上最長的天然接班人到達。

而且由於HashSet支持添加，刪除，更新O(1)時間。該算法將在O(n)時間內運行，其中n是輸入數組的長度。 在C＃中這種方法的代碼可以找到here