Trong thời gian ít tuyến tính, tìm bản sao trong một mảng được sắp xếp

Question

Hôm nay, một người phỏng vấn đã hỏi tôi câu hỏi này. Câu trả lời ngay lập tức của tôi là chúng ta có thể thực hiện tìm kiếm tuyến tính đơn giản, so sánh phần tử hiện tại với phần tử trước đó trong mảng. Sau đó ông hỏi tôi làm thế nào vấn đề có thể được giải quyết trong thời gian ít hơn tuyến tính.

Giả

• Mảng là sắp xếp
• chỉ một Có lặp lại
• Mảng là chỉ dân cư với số [0, n], nơi n là chiều dài của mảng.

Ví dụ mảng: [0,1,2,3,4,5,6,7,8,8,9]

Tôi đã cố gắng tìm ra một phân chia-và-chinh phục thuật toán để giải quyết điều này, nhưng tôi không tự tin rằng đó là câu trả lời đúng. Có ai có ý tưởng nào?

Answer 1

có thể được thực hiện trong thời gian O (log N) với một tìm kiếm nhị phân được sửa đổi:

Bắt đầu ở giữa của mảng: Nếu mảng [idx] < idx sự trùng lặp là sang bên trái, nếu không ở bên phải. Rửa sạch và lặp lại.

Answer 2

Tôi đã cố gắng đưa ra thuật toán phân chia và chinh phục để giải quyết vấn đề này, nhưng tôi không tự tin rằng đó là câu trả lời đúng.

Chắc chắn, bạn có thể thực hiện tìm kiếm nhị phân.

Nếu arr[i/2] >= i/2 thì bản sao nằm ở nửa trên của mảng, nếu không nó nằm ở nửa dưới.

while (lower != upper) 
    mid = (lower + upper)/2 
    if (arr[mid] >= mid) 
     lower = mid 
    else 
     upper = mid-1 

Kể từ khi mảng giữa lower và upper là giảm một nửa trong mỗi lần lặp, thuật toán chạy trong thời gian O (log n).

ideone.com demo in Java

Answer 3

Nếu không có số là mất tích từ mảng, như trong ví dụ này, nó doable trong thời gian O (log n) với một tìm kiếm nhị phân. Nếu a[i] < i, bản sao là trước i, nếu không thì sau i.

Nếu có một số vắng mặt và một bản sao, chúng tôi vẫn biết rằng nếu a[i] < i bản sao phải có trước khi i và nếu a[i] > i, số vắng mặt phải có trước khi i và trùng lặp sau. Tuy nhiên, nếu a[i] == i, chúng tôi không biết nếu số bị thiếu và trùng lặp đều là trước số i hoặc cả hai sau i. Tôi không nhìn thấy một cách cho một thuật toán sublinear trong trường hợp đó.

Answer 4

Mảng ví dụ hơi khác một chút so với câu hỏi của bạn. Vì n là chiều dài của mảng và có một và chỉ trùng lặp trong mảng, giá trị của mỗi phần tử trong mảng phải ở trong [0, n-1].

Nếu đó là sự thật, sau đó câu hỏi này là một trong những giống với How to find a duplicate element in an array of shuffled consecutive integers?

Các mã sau đây nên tìm ra trùng lặp trong O (n) thời gian và O (1) không gian.

public static int findOnlyDuplicateFromArray(int[] a, boolean startWithZero){ 
    int xor = 0; 
    int offset = 1; 
    for(int i=0; i < a.length; i++){ 
     if(startWithZero) 
      xor = xor^(a[i] + offset)^i; 
     else 
      xor = xor^a[i]^i; 
     } 
     if(startWithZero) 
      xor = xor - offset; 
    return xor; 
} 

Answer 5

Làm thế nào về điều đó? (phong cách đệ quy)

public static int DuplicateBinaryFind(int[] arr, int left, int right) 
{ 
    int dup =0; 

    if(left==right) 
    { 
     dup = left; 
    } 
    else 
    { 
     int middle = (left+right)\2; 
     if(arr[middle]<middle) 
     { 
      dup = DuplicateBinaryFind(arr,left, middle-1); 

     } 
     else 
     { 
      dup = DuplicateBinaryFind(arr, middle+1, right); 
     } 
    } 

    return dup; 

} 

Answer 6

Sự khác biệt giữa tổng các phần tử mảng đã cho và tổng các số tự nhiên từ 0 đến n-1 cung cấp cho bạn phần tử trùng lặp. Tổng các thành phần từ 0 đến n-1 là (N * N-1)/2 mảng mẫu là [0,1,2,3,4,5,6,7,8,8,9] tổng của 0 đến 9 số tự nhiên là: 45 tổng các phần tử mảng đã cho: 53 53-45 = 8 Yếu tố trùng lặp