Với 2 mảng sắp xếp các số nguyên, tìm số lớn nhất thứ n trong thời gian sublinear

Question

thể trùng lặp:
How to find the kth smallest element in the union of two sorted arrays?

Đây là một câu hỏi một người bạn của tôi nói với tôi ông đã được hỏi trong khi phỏng vấn, tôi đã suy nghĩ về một giải pháp.

Thời gian tuyến tính ngụ ý lôgarit với tôi, vì vậy có lẽ một số loại phương pháp phân chia và chinh phục. Để đơn giản, giả sử cả hai mảng đều có cùng kích thước và tất cả các phần tử là duy nhất

Answer 1

Tôi nghĩ rằng đây là hai tìm kiếm nhị phân đồng thời trên subarrays A[0..n-1] và B[0..n-1], đó là O (log n).

• mảng được sắp xếp Given, bạn biết rằng thứ n lớn nhất sẽ xuất hiện ở đâu đó trước hoặc tại A[n-1] nếu nó là trong mảng A, hoặc B[n-1] nếu nó là trong mảng B
• Hãy coi mục tại index a trong A và mục tại chỉ mục b trong B.
• Thực hiện tìm kiếm nhị phân như sau (giả khá thô, không dùng trong tài khoản 'một lần' vấn đề):
  • Nếu a + b > n, sau đó giảm việc tìm kiếm thiết
    • nếu A[a] > B[b] sau đó b = b/2, khác a = a/2
  • Nếu a + b < n, sau đó tăng việc tìm kiếm thiết
    • nếu A[a] > B[b] rồi b = 3/2 * b, khác a = 3/2 * a (nằm giữa a và trước a)
  • Nếu a + b = n thì thứ n lớn nhất là max(A[a], B[b])

tôi tin rằng trường hợp O (ln n) tồi tệ nhất, nhưng trong bất kỳ trường hợp chắc chắn sublinear.

Answer 2

Tôi tin rằng bạn có thể giải quyết vấn đề này bằng cách sử dụng biến thể trên tìm kiếm nhị phân. Trực giác đằng sau thuật toán này là như sau. Hãy để hai mảng là A và B và giả sử vì mục đích đơn giản là chúng có cùng kích thước (điều này là không cần thiết, như bạn sẽ thấy). Đối với mỗi mảng, chúng ta có thể xây dựng các mảng song song Ac và Bc sao cho cho mỗi chỉ số i, Ac [i] là số phần tử trong hai mảng không lớn hơn A [i] và Bc [i] là số các phần tử trong hai mảng không lớn hơn B [i]. Nếu chúng ta có thể xây dựng các mảng này một cách hiệu quả, thì chúng ta có thể tìm thấy phần tử nhỏ nhất thứ k một cách hiệu quả bằng cách thực hiện tìm kiếm nhị phân trên cả Ac và Bc để tìm giá trị k. Mục nhập tương ứng của A hoặc B cho mục nhập đó là phần tử lớn nhất thứ k. Tìm kiếm nhị phân là hợp lệ vì hai mảng Ac và Bc được sắp xếp, mà tôi nghĩ bạn có thể thuyết phục bản thân khá dễ dàng.

Tất nhiên, giải pháp này không hoạt động trong thời gian tuyến tính vì phải mất O (n) thời gian để xây dựng mảng Ac và Bc. Câu hỏi sau đó là - có cách nào để chúng tôi có thể ngầm định xây dựng các mảng này không? Đó là, chúng ta có thể xác định các giá trị trong các mảng này mà không nhất thiết phải xây dựng từng phần tử không? Tôi nghĩ rằng câu trả lời là có, sử dụng thuật toán này. Hãy bắt đầu bằng cách tìm kiếm mảng A để xem nó có giá trị nhỏ nhất kth hay không. Chúng ta biết rằng một giá trị nhỏ nhất thứ k không thể xuất hiện trong mảng trong mảng A sau vị trí k (giả sử tất cả các phần tử là khác nhau). Vì vậy, chúng ta hãy chỉ tập trung vào các phần tử k đầu tiên của mảng A. Chúng ta sẽ thực hiện tìm kiếm nhị phân trên các giá trị này như sau. Bắt đầu tại vị trí k/2; đây là phần tử nhỏ nhất k/2 trong mảng A. Bây giờ thực hiện tìm kiếm nhị phân trong mảng B để tìm giá trị lớn nhất trong B nhỏ hơn giá trị này và nhìn vào vị trí của nó trong mảng; đây là số phần tử trong B nhỏ hơn giá trị hiện tại. Nếu chúng ta thêm vị trí của các phần tử trong A và B, chúng ta có tổng số phần tử trong hai mảng nhỏ hơn phần tử hiện tại. Nếu đây chính xác là k, chúng ta đã xong. Nếu giá trị này nhỏ hơn k, thì chúng tôi sẽ chấp nhận nửa trên của các phần tử k đầu tiên của A và nếu điều này lớn hơn k, chúng tôi chấp nhận ở nửa dưới của các phần tử đầu tiên của k, v.v. Cuối cùng, chúng tôi sẽ thấy rằng phần tử lớn thứ k nằm trong mảng A, trong trường hợp này chúng ta đã hoàn thành. Nếu không, lặp lại quá trình này trên mảng B.

Thời gian chạy cho thuật toán này như sau. Việc tìm kiếm mảng A thực hiện tìm kiếm nhị phân trên các phần tử k, nó lấy các phép lặp O (lg k). Mỗi phép lặp giá thành O (lg n), vì chúng ta phải thực hiện tìm kiếm nhị phân trong B. Điều này có nghĩa là tổng thời gian cho tìm kiếm này là O (lg k lg n). Thời gian thực hiện điều này trong mảng B là như nhau, do đó thời gian chạy ròng cho thuật toán là O (lg k lg n) = O (lg n) = o (n), là tuyến dưới.

Answer 3

Dư tuyến mặc dù là gì? Bạn không thể có một thuật toán không kiểm tra ít nhất n phần tử, thậm chí việc xác minh một giải pháp sẽ yêu cầu kiểm tra nhiều. Nhưng kích thước của vấn đề ở đây chắc chắn có nghĩa là kích thước của các mảng, do đó, một thuật toán chỉ kiểm tra các phần tử n là tuyến dưới.

Vì vậy, tôi nghĩ rằng không có trick ở đây, bắt đầu với danh sách với các yếu tố khởi đầu nhỏ hơn và tiến bộ cho đến khi bạn có:

1. Tiếp cận các yếu tố thứ n, và bạn đã hoàn tất.
2. Tìm phần tử tiếp theo lớn hơn phần tử tiếp theo trong danh sách khác, tại thời điểm đó bạn chuyển sang danh sách khác.
3. Hết bộ phận và chuyển đổi.

Answer 4

int[] a = new int[] { 11, 9, 7, 5, 3 }; 
int[] b = new int[] { 12, 10, 8, 6, 4 }; 
int n = 7; 
int result = 0; 
if (n > (a.Length + b.Length)) 
    throw new Exception("n is greater than a.Length + b.Length"); 
else if (n < (a.Length + b.Length)/2) 
{ 
    int ai = 0; 
    int bi = 0; 
    for (int i = n; i > 0; i--) 
    { 
     // find the highest from a or b 
     if (ai < a.Length) 
     { 
      if (bi < b.Length) 
      { 
       if (a[ai] > b[bi]) 
       { 
        result = a[ai]; 
        ai++; 
       } 
       else 
       { 
        result = b[bi]; 
        bi++; 
       } 
      } 
      else 
      { 
       result = a[ai]; 
       ai++; 
      } 
     } 
     else 
     { 
      if (bi < b.Length) 
      { 
       result = b[bi]; 
       bi++; 
      } 
      else 
      { 
       // error, n is greater than a.Length + b.Length 
      } 
     } 
    } 
} 
else 
{ 
    // go in reverse 
    int ai = a.Length - 1; 
    int bi = b.Length - 1; 
    for (int i = a.Length + b.Length - n; i >= 0; i--) 
    { 
     // find the lowset from a or b 
     if (ai >= 0) 
     { 
      if (bi >= 0) 
      { 
       if (a[ai] < b[bi]) 
       { 
        result = a[ai]; 
        ai--; 
       } 
       else 
       { 
        result = b[bi]; 
        bi--; 
       } 
      } 
      else 
      { 
       result = a[ai]; 
       ai--; 
      } 
     } 
     else 
     { 
      if (bi >= 0) 
      { 
       result = b[bi]; 
       bi--; 
      } 
      else 
      { 
       // error, n is greater than a.Length + b.Length 
      } 
     } 
    } 
} 
Console.WriteLine("{0} th highest = {1}", n, result); 

Answer 5

Đây là câu trả lời khá giống với câu trả lời của Kirk.

Gọi Find(nth, A, B) là hàm trả về số thứ n và | A | + | B | > = n. Đây là mã giả đơn giản mà không kiểm tra nếu một mảng nhỏ, nhỏ hơn 3 phần tử. Trong trường hợp mảng nhỏ một hoặc hai tìm kiếm nhị phân trong mảng lớn hơn là đủ để tìm phần tử cần thiết.

Find(nth, A, B) 
    If A.last() <= B.first(): 
    return B[nth - A.size()] 
    If B.last() <= A.first(): 
    return A[nth - B.size()] 
    Let a and b indexes of middle elements of A and B 
    Assume that A[a] <= B[b] (if not swap arrays) 
    if nth <= a + b: 
    return Find(nth, A, B.first_half(b)) 
    return Find(nth - a, A.second_half(a), B) 

Đó là log(|A|) + log(|B|), và vì mảng đầu vào có thể được thực hiện để có n yếu tố mỗi nó là log(n) phức tạp.