Эффективный способ проверить, содержит ли список случайных чисел диапазон от 1 до n

Question

Если у меня есть произвольно перемешанный массив с номерами от 1 до n, какой хороший способ найти, что массив содержит диапазон от 1 до n (без повторов)? Например,

n = 6; [1, 3, 6, 2, 4, 5] => true
n = 6; [1, 1, 2, 4, 5, 6] => false

Answer 1

Звучит подозрительно, как домашнее задание, но ...

Это очень просто с помощью набора:

/* Convert to your favorite language */

validateArray(a, n) {
  assertEqual(n, a.length)
  def s = new Set(a); // set with all elements of a
  assertEqual(s, Set(1..n)); // should be equal to set containing 1 to n
}

Answer 2

Создайте массив размером n, пройдите через ваш массив и увеличьте позицию в массиве в качестве индекса.Если в любое время массив счетчиков имеет не 0 или не 1 значение, вы можете остановиться.Если вы не можете найти индекс, вы можете остановиться сейчас, так как знаете, что у вас его нет.

Вот краткий пример Java.В этом примере вам не нужно считать в конце, потому что все, что приведет к значению, отличному от 1, приведет к сбою в середине.

boolean isRange(int[] arr) {

    int[] counts = new int[arr.length];

    for(int i : arr) {
        if(i < 1 || i > arr.length) return false;
        if(counts[i - 1] != 0) return false;
        counts[i-1] = 1;
    }
    return true; // if it wasn't, we would have failed by now

}

Answer 3

Если дополнительное пространство не разрешено (типичное ограничение в вопросе об интервью), то вы можете сначала отсортировать массив и последовательно сканировать отсортированный массив слева направо, чтобы увидеть, больше ли каждый элемент, чем предыдущий элемент, на 1. временная сложность O (n * logn).

Answer 4

Вы хотите отсортировать массив. Вот ссылка на некоторые популярные варианты, http://en.wikipedia.org/wiki/Sorting_algorithm. Лично я рекомендую пузырьковую сортировку для простого решения и сортировку слиянием для более жесткой и быстрой версии.

После того, как список отсортирован, вы можете проверить повторы, выполнив итерацию по массиву и убедившись, что следующий # больше предыдущего. Кроме того, это может быть добавлено к сортировке, чтобы сократить время вычислений.

Наконец, проверьте первое и последнее числа, чтобы убедиться, что они равны 1 и n.

Answer 5

Используйте формулу Гаусса, чтобы предварительно вычислить, какой будет конечная сумма:

final_sum = k * (k+1)
            ---------
                2

Сделайте линейный цикл над вашим перемешанным списком, добавляя числа по мере того, как вы идете, и, если ваша текущая сумма совпадает с вашей окончательной суммой, возвращает true.