Tìm phần tử trùng lặp trong một mảng các số nguyên liên tiếp trong thời gian O (log n)

Question

Một vài ngày trước, trong một cuộc phỏng vấn, tôi được hỏi một chương trình tìm phần tử trùng lặp trong một dãy số nguyên liên tiếp trong thời gian O(log n) .

Trường hợp hơi cụ thể, vì có tổng cộng 11 số nguyên (1 đến 10, theo thứ tự) đó, một bản sao của bất kỳ số nào trong số này được chèn vào đâu đó ở giữa.

tôi đã được đưa ra một mẫu tương tự như sau:

{1, 2, 3, 4, 5, 6, , 7, 8, 9, 10}

Vì vậy, bây giờ tôi đã đưa ra mã C sau:

#include <stdio.h> 

int main (void) 
{ 
    int a[11] = {1, 2, 3, 4, 5, 6, 2, 7, 8, 9, 10}, first=0, last=10, mid; 

    while (1) 
    { 
     mid = (first + last)/2; 

     if (mid+1 == a[mid]) 
      first = mid+1; 

     else if ((mid == 0) || (mid == 10) || (a[mid+1] - a[mid-1] == 1)) /* Order is Important, (a[mid+1] - a[mid-1] == 1) must be last */ 
      break; 

     else 
      last = mid-1; 
    } 

    printf("Duplicate element is %d, located at position no. %d.", a[mid], mid+1); 

    return 0; 
} 

Điều này có đáp ứng đúng tiêu chuẩn O(log n) không? Và, có bất kỳ lựa chọn thay thế/cải tiến nào về điều này không?

Answer 1

Có, nó có độ phức tạp thời gian là O(log n).

Có thể làm cho đoạn code rõ ràng hơn bằng cách sử dụng thực tế như sau: bạn cần phải tìm nhỏ nhất i mà a[i] != i + 1, vì vậy nó có thể được thực hiện một cách ngắn gọn hơn:

//invariant: the [0...low] prefix does not contain a duplicate 
//   the [0...high] prefix contains a duplicate 
low = 0 //[0...0] prefix obviously does not contain a duplicate 
high = 10 //the entire array obviously contains a duplicate 
while high - low > 1: 
    mid = (low + high)/2 
    if a[mid] != mid + 1: 
     high = mid 
    else: 
     low = mid 
print(a[high], high) 

Answer 2

Chúng tôi có thể sửa đổi số binary search algorithm để nhận giải pháp. Trong binary search, chúng tôi có một chìa khóa và chúng tôi sử dụng phím này để tìm vị trí của nó bằng cách chia đôi kích thước mảng. Ở đây, chúng ta không có chìa khóa, thay vào đó chúng ta phải tìm ra nó. Nhưng hành vi của duplicate element có thể được sử dụng để bisect kích thước mảng. Làm sao ? cho phép xem:

On cẩn thận tìm kiếm dữ liệu, chúng ta có thể dễ dàng thấy rằng sau khi chèn các yếu tố trùng lặp ở vị trí ngẫu nhiên (nói index) trong mảng nguyên tố liên tiếp là tài sản của các yếu tố sẽ thay đổi (a[i] == i+1 ->a[i] != i+1) từ vị trí index (bao gồm index). Bây giờ thuộc tính đã thay đổi này có thể được sử dụng để chia đôi kích thước mảng. Do đó, chúng ta có thể tìm ra bản sao trong O(log(n)).

Ví dụ, xem xét mảng cho bạn: {1, 2, 3, 4, 5, 6, 2, 7, 8, 9, 10}

{1, 2, 3, 4, 5, 6, 2, 7, 8, 9, 10} 
          || 
          from this position the the property of (a[i] == i+1) will no more satisfied. 

tài sản này có thể là mô hình để chia hai nga kích thước mảng trong dung dịch.

void binary_duplictae_finder(int a[], int low, int high) { 

    int mid=(low+high)/2; 

    if(high - low > 1){ 
      if(a[mid]!=mid+1) 
       binary_duplictae_finder(a, low, mid); 
      else 
       binary_duplictae_finder(a, mid, high); 
    } 

    if(high==low+1) 
     printf("%d ", a[high]); 
}