Минимальное положительное пропущенное целое число из данного массива - PullRequest
Новая
       16

Минимальное положительное пропущенное целое число из данного массива

0 голосов
/ 30 мая 2018

Я хочу найти минимальное положительное целое число, отсутствующее в массиве со сложностью 'n' времени.Является ли это возможным?Например, пусть {-3, -6,1, -9,4,6,0} - это наш массив, тогда минимальное положительное целое число будет 2.

1 Ответ

0 голосов
/ 30 мая 2018

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

bool arr_check [ARR_SIZE];    // whick numbers has been found.
for (int i=0; i<ARR_SIZE; i++)
    if(arr[i]>0)
        arr_check[arr[i]] = true;
for (int i=0; i<ARR_SIZE; i++)
    if (!arr_check[i])
        return i;

Вам нужно будет только дважды просмотреть массив, что придает ему сложность '2N', верно?Вы не получите его быстрее без предварительной сортировки, что больше, чем «N»

...