найти наименьшее целое число, которое не является в массиве

Question

Учитывая несортированный набор A, что является наиболее эффективным решением для нахождения наименьшего целого числа x, которое не является элементом A такой, что x потребности быть больше некоторого целого m?

например.

Вход: A = {7, 3, 4, 1}, m = 5

Выход: x = 6

Я ищу решение в C, но любой вид псевдокоде будет полезно ... Может быть решена эта проблема в О (п) где n - заданный размер?

Answer 1

Я решил использовать его и добавить массив. Здесь «len» - длина массива.

int findMin(int *arr,int n,int len) 
{ 
    int *hash; 
      if(len==0) 
       {return -1; //fail 
       } 
    hash=(int*)calloc(len,sizeof(int)); //hash function I'm using is f(x)=f(x)-n; 
    int i; 
    for(i=0;i<len;i++){ 
     if(arr[i]>n && arr[i]<len+n){ //because max element can't be more than n 
      hash[arr[i]-n]++; 
     } 
    } 

    i=1; 
    while(i<len){ 
     if(hash[i]==0) 
      return len+i; 
     i++; 
    } 
      return len+n+1; 
} 

Порядок этой души - это время работы O (n) и O (n).

Answer 2

Следующий код Java должен работать для вас:

public static int findMinNotInArray(int array[], int n) { 
    int frequency[] = new int[array.length]; 

    if (n < max(array)) { 
     for (int i = 0; i < array.length; i++) { 
      if (array[i] > n && array[i] < n + array.length) 
       frequency[array[i] - (n + 1)]++; 
     } 

     for (int i = 0; i < frequency.length; i++) { 
      if (frequency[i] == 0) 
       return i + n + 1; 
     } 
     return -1; 
    } else { 
     return n + 1; 
    } 
} 

public static int max(int array[]) { 
    int max = array[0]; 
    for (int i = 1; i < array.length; i++) { 
     if (array[i] > max) { 
      max = array[i]; 
     } 
    } 
    return max; 
} 

Приведенный выше код просто отслеживает число от n+1 к (n+1) + lengthOfA ли какой-либо один из этого диапазона присутствует в массиве или нет! И возвращает первый неподходящий номер!

Answer 3

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

Сложность этого подхода заключается в том, что алгоритм сортировки, а именно O (nlogn), в большинстве случаев.