如何檢查一組數字是否有空隙？

Question

我有很長的陣列，這些數字：

long[] = {1,2,3,5,6,7}; 

注意4丟失。 如果存在或不存在任何此類差距，測試此陣列的最佳方法是什麼？

Answer 1

循環遍歷數組並檢查，如果當前項正好比當前索引多x，其中x是數組中的第一個元素。

public boolean hasGaps(long[] array) { 
    if(array == null || array.length == 0) { 
     return false; 
    } 

    long start = array[0]; 
    for(int i = 0; i < array.length; i++) { 
     if(array[i] != i + start) { 
      return true; 
     } 
    } 
    return false; 
} 

Answer 2

public static boolean hasGaps(long[] array) { 
    if (array == null || array.length == 0) { 
     return false; 
    } 
    if (array[array.length - 1] - array[0] + 1 != array.length) { 
     return true; 
    } 
    for (int i = 1; i < array.length; i++) { 
     if (array[i] != array[i - 1] + 1) { 
      return true; 
     } 
    } 
    return false; 
} 

此方法首先檢查「容易」的情況下，然後迭代陣列檢查更復雜的情況。

Answer 3

如果要保證陣列在沒有任何重複的命令，那麼你可以檢查在O（1）

我認爲此代碼應在此特定情況下:)

long[] myarray = generateOrderedNoDuplicateArray(); 

.... 

    public boolean checkHasGap(long[] array) { 
    if (array.length == 0) { 
     return false; 
    } else { 
     return array[0] + array.length == array[array.length - 1] + 1; 
    } 
    } 

Answer 4

工作假設數組值是沒有排序，而不是唯一的，你寫的檢查功能：

• 每個值只出現一次
• 最大值 - 最小值+ 1等於陣列長度

在一次迭代中計算最大值和最小值是非常簡單的。至於檢查重複項，您可以使用任何允許您檢查值是否存在的集合。

public static boolean isContiguous(long[] array) { 
    Set <Long> hashset = new HashSet <Long>(); 
    long min = array[0]; 
    long max = array[0]; 
    for (int i = 0; i < array.length; i++) { 
     if (hashset.add(array[i]) == false) return false; 
     if (min > array[i]) min = array[i]; 
     if (max < array[i]) max = array[i]; 
    } 
    return max - min + 1 == array.length; 
} 

IDEONE