Как проверить, имеет ли массив чисел пробелы?

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