Поиск недостающего числа в несортированном массиве с повторяющимися значениями

Question

У меня есть массив размером «n» с unsorted и reapeated integers между [0-99]. Я уже знаю, что одного номера нет. Итак, каков самый быстрый способ найти недостающее число? Это мое решение до сих пор в С.

int find_missing_number(int array[], int n) 
{ 
    char checker[100] = {0}; 
    int xor = 0, counter = 0, i, temp; 
    //xor = (n%4==0) ? 0 : (n%4==1) ? n-1 : (n%4==2) ? 1 : n; 

    for(i = 0; i < n; i++) 
     if(checker[temp = array[i]] == 0) 
     { 
      checker[temp] = 1; 
      xor ^= temp; 
      if(++counter == 99) 
       return xor; 
     } 

    return -1; 
} 

Answer 1

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

Я бы предположил, что вместо того, чтобы разбирать элементы, вы можете просто прочитать массив проверки, чтобы найти отсутствующий элемент.

int find_missing_number(int array[], int n)  
{ 
    int checker[100] = {0}; 

    for(int i = 0; i < n; i++) 
     checker[array[i]]++; 

    for(int i=0; i <100; i++) 
     if(0 == checker[i]) 
      return i; 
} 

Это уменьшит операции, которые зависят от n, делая код быстрее для большего n.

Answer 2

Вы можете сделать это в O (n). Перейдем через массив и вычислим сумму всех чисел. Теперь сумма натуральных чисел от 1 до N может быть выражена как Nx (N + 1)/2. В вашем случае N = 99. Вычтите сумму массива из Nx (N + 1)/2, где N = 99. Это недостающее число. Пустой слот может быть обнаружен во время итерации, в которой вычисляется сумма.

Я не совсем уверен, если это более быстрый метод или нет, но вариант для вас попробовать.

Редактировать: Это будет работать, если у вас не было повторяющихся значений.

Answer 3

Учитывая, что у вас могут быть дубликаты, я не вижу никакого способа сохранить какую-то запись, какие значения были замечены, которую вы можете прочитать на основе стоимости. Подходы, основанные на одном и том же разновидности односторонней хэширующей функции (два из которых были предложены, а затем убраны), не могут выполнять свою работу самостоятельно. Может быть, однако, что вы можете сэкономить усилия сканирования вашей записи замеченных значений после заполнения ее, объединив ее с хэш-подобной функцией. Например,

int find_missing_number(int array[], int n) 
{ 
    char checker[100] = {0}; 
    int xor = XOR_OF_1_TO_100; 
    int i; 

    for(i = 0; i < n; i++) { 
     xor ^= (checker[array[i]] ? 0 : array[i] + 1); 
     checker[array[i]] = 1; 
    } 

    return xor - 1; 
} 

Это правда очень похожа на вашу версию, но я более уверен, что он будет работать, и я думаю, что это, вероятно, работает немного быстрее.

Отметьте, что я не объявляю никаких переменных register - компилятор намного лучше, чем я, когда вы выбираете, какие переменные должны проживать в реестрах, а какие нет, и он не обязан брать мой совет по этому вопросу в любом случае ,

Кроме того, элементы checker массива имеют тип char, что позволяет в четыре раза больше, чтобы находиться в строке кэша процессора сразу, чем если бы они были типа int (предполагая, что 1-байтовое char с и 4-байтовый int ы) ,

Обратите внимание, что я избегаю подсчета различных значений или иначе ветвящихся внутри цикла (тройное выражение может быть реализовано без ветки). Избегание счетного и условного оператора ускорит случай, когда действительно отсутствует одно значение, и может или не может на практике замедлить случай, когда ни один отсутствует. Коэффициент усиления может возникнуть из-за того, что он не имеет меньше кода - иногда такие упрощения могут позволить компилятору генерировать более эффективные последовательности команд.

Конечно, все дело в нежелательной (и проблема не указана), если может отсутствовать более одного значения.

Answer 4

Оригинальная программа уже очень быстро. Однако, учитывая постановка проблемы, это может быть сделано быстрее, изменив следующим образом:

 if(++counter == 100) 
      return -1; 

к этому:

 if(++counter == 99) 
      return xor; 

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

Answer 5

У Javia1492 была основная идея в его ответе: суммирование чисел.

Аргумент checker не позволяет суммировать вдвое большее число.

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

Он также работает с оператором xor, как и вы, но мне это не очень нравится, потому что 1^2^3^..^99 == 0 - это своего рода частный случай, с которым вы не можете обобщить 1^2^..^N.

int find_missing_number(int array[], int n) 
{ 
    char checker[100]; 
    register int sum = 0, counter = 0, i, temp; 

    memset(checker, 0, sizeof(checker)); 
    for (i = 0; i < n; i++) 
    { 
     if (checker[temp = array[i]] == 0) 
     { 
      checker[temp] = 1; 
      sum += temp; 
      if (++counter == 99) 
       break; 
     } 
    } 
    return 4950 - sum; // (100*99)/2 - sum 
}