Tìm số nguyên nhỏ nhất mà không phải là trong một mảng

Question

Với một bộ không được phân loại A giải pháp hiệu quả nhất cho việc tìm kiếm các số nguyên nhỏ nhất x mà không phải là yếu tố A mà x nhu cầu để được lớn hơn một số nguyên m là gì?

ví dụ:

Input: A = {7, 3, 4, 1}, m = 5

Output: x = 6

tôi đang tìm kiếm giải pháp trong C, nhưng bất kỳ loại giả sẽ là hữu ích ... Có thể vấn đề này được giải quyết trong thời gian O (n) trong đó n là kích thước thiết lập?

Answer 1

Tôi đã giải quyết nó bằng cách sử dụng và mảng phụ. Hiện tại 'len' là chiều dài của mảng.

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; 
} 

Thứ tự của linh hồn này là thời gian chạy O (n) và không gian O (n).

Answer 2

Mã Java sau nên làm việc cho bạn:

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; 
} 

Đoạn mã trên chỉ đơn giản là theo dõi các số từ n+1 đến (n+1) + lengthOfA dù bất kỳ một từ cự ly này hiện diện trong mảng hay không! Và trả về số không hiện tại đầu tiên!

Answer 3

Tôi nghĩ, cách tiếp cận khả thi nhất là sắp xếp mảng đầu tiên. Sau đó, bạn có thể thực hiện tìm kiếm nhị phân cho m trong đó, tiếp theo là tìm kiếm tuyến tính cho điểm tiếp theo nơi hàng xóm cách nhau nhiều hơn.

Tính phức tạp của phương pháp này là thuật toán sắp xếp, nghĩa là O (nlogn) trong hầu hết các trường hợp.