проверка массива - без использования вспомогательного массива

Question

Этот вопрос для настоящих брейнхаков, потому что это нужно делать без вспомогательного массива. и должен быть максимально эффективным!

Программа

C - необходимо получить массив с числами X (предположим, массив X = 4: 5,4,3,2) и проверьте, есть ли в массиве все числа от 0 до X-1 (Если X равен 44, необходимо проверить, все ли числа в диапазоне от 0 до 43 внутри массива).

Это должно быть супер эффективно - я имею в виду, запускать массив 43 раза - это не вариант!

Ты хоть представляешь, как это сделать ?? Я пытаюсь понять это часами без какого-либо успеха !!

Должно быть O (n).

Answer 1

Если разрешено изменение порядка массива, вы можете использовать алгоритм сортировки по месту, а затем проверить, если для некоторого i:

array[i] == array[i+1]

Тогда сложность времени может быть O (n * lg n).

Answer 2

Сортировка обоих массивов (в O(n log n)).Затем обработайте оба массива как очереди:

1. Если элементы заголовка обеих очередей равны, выведите один из них и вставьте оба.
2. Если элементы головы не равны, выведите меньшее.
3. Повтор.

Answer 3

Вы можете упростить задачу для поиска дубликатов.

Доказательство:

• Если длина массива не равна X => Отсутствуют числа.Вы можете легко проверить, что в O (1) или O (n).
• Else => у вас либо все правильные числа, либо есть дубликаты.Можно использовать эту реализацию: Поиск дубликатов за O (n) времени и O (1) пространства .Также убедитесь, что вы проверите границы массива.Если числа не находятся внутри границ, массив содержит неправильные числа.

  Это приводит к решению O (n).

Answer 4

Сортируйте по меньшему и используйте бинарный поиск для поиска каждого элемента в большем.Таким образом, вы можете сделать это в O((n1+n2)*log(n1)), где n1, n2 - размеры массивов (n1 - меньше).

Answer 5

Вы можете сделать [в среднем случае] лучше, чем предлагаемое O(nlogn) решение.
Существует O(n) решение для среднего случая с использованием моторизованного оружия с использованием хеш-таблиц:

hash <- new hash set
for each e in A:
  hash.add(e)
for each e in B:
  if hash.contains(e): print e

Вы можете преодолеть печать элементов дважды, если они дважды появляются в букве B, сохранив дополнительный хэш-набор «напечатанных» элементов.

Если проблема с задержкой или наихудшим случаем является проблемой, используйте один из предложенных вариантов и повторите предложенные решения.

Answer 6

Вы можете использовать модифицированную операцию слияния (например, ту, которая используется в mergesort), если массивы отсортированы.

Answer 7

решение O (n): алгоритм пытается поместить каждый элемент в массиве в правильную позицию, например, 1 на a [0] и 2 на a [1], путем замены на элемент занимает исходную позицию.

сначала, я = 1, a [i - 1] = 1, все в порядке, и ничего не будет затронуто

i = 1
a = 1 6 3 4 5 7 1 

тогда, i = 2, a [i - 1] = 6! = 2, затем поменяйте местами a [i - 1] и a [6 - 1]

i = 2 
a = 1 7 3 4 5 6 1

тогда я по-прежнему равен 2, но a [i - 1] == 7! = 2, затем поменяйте местами a [i - 1] и a [7 - 1]

i = 2
a = 1 1 3 4 5 6 7

теперь i = 2, но мы видим, что a [i - 1] == a [1 - 1], поэтому мы находим дубликат

полный источник:

#include <stdio.h>

int main() {
    int a[7] = {1, 6, 3, 4, 5, 7, 1};
    int i, t;
    for (i = 0; i < 7; ++i) {
        while (a[i] != i + 1) {
            if (a[i] == a[a[i] - 1]) {
                printf("duplicate: %d\n", a[i]);
                goto out;
            } 
            t = a[i];
            a[i] = a[a[i] - 1];
            a[t - 1] = t;
        }
    }
    printf("no duplicate\n");
out:
    return 0;
}

Answer 8

foreach(int i in array)
{
    int count = 0;
    foreach(int i2 in array)
    {
        if(i == i2)
        {
            count++;
        }
    }
    if(count > 1)
    {
        return false;
    }
}

return true;

Answer 9

См. Некоторые блестящие ответы здесь , реализация ответа Caf на C ++ может быть bool stop=true; // сначала поместите элемент i в местоположение A [i], то есть 4 в A [4]

for(int  i = 0; i<n; i++) {
    while (A[A[i]] != A[i]){ 
        swap(A[i], A[A[i]])
    }
}
// than u can have the second loop which does the decision 
for(int  i = 0; i<n && !stop; i++) {
    if (A[i] != i){ 
        stop = true;
    }
}

if (stop)
    printf("duplicate");
else
   printf("not duplicate)

Answer 10

Прочтите это для ответа - проверка массива - без использования вспомогательного массива

массив из n элементов, который содержит элементы от 0 до n-1, причем любое из этих чисел появляется любое количество раз.

Например, пусть n будет 7, а массив {1, 2, 3, 4, 5, 4, 6}, ответ должен быть ЛОЖЬ

Разве вышеприведенные утверждения не противоречат самим себе ?!