Median of Lists

Question

Tôi được hỏi câu hỏi này:

Bạn có hai danh sách số nguyên, mỗi danh sách được sắp xếp theo thứ tự tăng dần và mỗi giá trị có độ dài n. Tất cả các số nguyên trong hai danh sách đều khác nhau. Bạn muốn tìm phần tử nhỏ nhất thứ n của liên minh của hai danh sách. (Tức là, nếu bạn nối các danh sách và sắp xếp danh sách kết quả theo thứ tự tăng dần, phần tử sẽ ở vị trí thứ n.)

Giải pháp của tôi: Giả sử danh sách được lập chỉ mục 0.

Giải pháp O (n): Một giải pháp thẳng về phía trước là quan sát các mảng đã được sắp xếp, vì vậy chúng tôi có thể hợp nhất và dừng sau n bước. Các phần tử n-1 đầu tiên không cần phải được sao chép vào một mảng mới, vì vậy giải pháp này có thời gian O (n) và O (1).

Giải pháp O (log2 n): Giải pháp O (log2 n) sử dụng thay thế tìm kiếm nhị phân trên mỗi danh sách. Tóm lại, nó lấy phần tử trung gian trong khoảng thời gian tìm kiếm hiện tại trong danh sách đầu tiên (l1 [p1]) và tìm kiếm nó trong l2. Vì các phần tử là duy nhất, chúng ta sẽ tìm thấy tối đa 2 giá trị gần nhất với l1 [p1]. Tùy thuộc vào giá trị của chúng tương ứng với l1 [p1-1] và l1 [p1 + 1] và chỉ số của chúng p21 và p22, chúng tôi trả về phần tử thứ n hoặc recurse: Nếu tổng của bất kỳ giá trị nào trong số (tối đa) 3 chỉ số trong l1 có thể được kết hợp với một trong hai (nhiều nhất) 2 chỉ số trong l2 sao cho l1 [p1 '] và l2 [p2'] sẽ nằm ngay cạnh nhau trong liên kết được sắp xếp của hai danh sách và p1 '+ p2 '= n hoặc p1' + p2 '= n + 1, chúng tôi trả về một trong 5 phần tử. Nếu p1 + p2> n, chúng tôi chấp nhận lại một nửa khoảng thời gian tìm kiếm trong l1, nếu không chúng tôi sẽ chuyển sang khoảng thời gian phù hợp. Bằng cách này, cho ra khỏi O (log n) có thể midpoints trong l1 chúng tôi làm một O (log n) nhị phân tìm kiếm trong l2. Do đó thời gian chạy là O (log2 n).

O (log n) giải pháp: Giả sử danh sách l1 và l2 có thời gian truy cập thường xuyên đến bất kỳ yếu tố của họ, chúng tôi có thể sử dụng một phiên bản sửa đổi của tìm kiếm nhị phân để có được một O (log n) giải pháp. Cách tiếp cận dễ nhất là tìm kiếm chỉ mục p1 chỉ trong một trong các danh sách và tính chỉ mục tương ứng p2 trong danh sách khác để p1 + p2 = n vào mọi lúc. (Điều này giả định rằng các danh sách được lập chỉ mục từ 1.) Đầu tiên chúng tôi kiểm tra trường hợp đặc biệt khi tất cả các phần tử trong một danh sách nhỏ hơn bất kỳ phần tử nào trong danh sách khác: Nếu l1 [n] < l2 [0] return l1 [n ]. Nếu l2 [n] < l1 [0] trả lại l2 [n]. Nếu chúng ta không tìm thấy phần tử nhỏ nhất n-thứ sau bước này, hãy gọi findNth (1, n) với giả xấp xỉ:

findNth(start,end) 
p1 = (start + end)/2 
p2 = n-p1 
if l1[p1] < l2[p2]: 
    if l1[p1 + 1] > l2[p2]: 
     return l2[p2] 
    else: 
     return findNth(p1+1, end) 
else: 
    if l2[p2 + 1] > l1[p1]: 
     return l1[p1] 
else: 
    return findNth(start,p1-1) 

tử l2 [p2] được trả về khi l2 [p2] lớn hơn chính xác các yếu tố p1 + p2-1 = n-1 (và do đó là phần tử thứ n nhỏ nhất). l1 [p1] được trả về trong cùng điều kiện nhưng đối xứng. Nếu l1 [p1] < l2 [p2] và l1 [p1 + 1] < l2 [p2], thứ hạng l2 [p2] lớn hơn n, vì vậy chúng ta cần lấy nhiều phần tử từ l1 trở xuống từ l2. Vì vậy, chúng tôi tìm kiếm p1 ở nửa trên của khoảng thời gian tìm kiếm trước đó. Mặt khác, nếu l2 [p2] < l1 [p1] và l2 [p2 + 1] < l1 [p1], thứ hạng của l1 [p1] lớn hơn n. Do đó, p1 thực sẽ nằm trong nửa dưới của khoảng thời gian tìm kiếm hiện tại của chúng tôi. Vì vậy, chúng tôi giảm một nửa kích thước của sự cố tại mỗi cuộc gọi đến findNth và chúng tôi chỉ cần làm việc liên tục để giảm một nửa kích thước sự cố, sự lặp lại của thuật toán này là T (n) = T (n/2) + O (1), trong đó có một giải pháp O (log n) -time.

Người phỏng vấn liên tục hỏi tôi các cách tiếp cận khác nhau cho vấn đề trên. Tôi đã đề xuất ba phương pháp tiếp cận trên.Chúng có chính xác không? Có giải pháp nào khác tốt nhất có thể cho câu hỏi này không? Trên thực tế câu hỏi này được hỏi rất nhiều lần vì vậy xin vui lòng cung cấp một số công cụ tốt về nó.

Answer 1

Không chắc chắn nếu bạn đã xem xét điều này: http://www.leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html

Đó giải quyết một phiên bản tổng quát hơn của vấn đề bạn đang hỏi về. Chắc chắn độ phức tạp của nhật ký là có thể ...

Answer 2

Tôi nghĩ đây sẽ là giải pháp tốt nhất. .

->1 2 3 4 5 6 7 8 9 
->10 11 12 13 14 15 16 17 18 

mất hai con trỏ i và j mỗi chỉ vào đầu mảng, tăng i nếu a [i] < b [j]

increment j nếu a [i]> b [j ]

thực hiện việc này n lần.

tuyến tính O (n) O (1) giải pháp không gian.