Ví dụ ar1=[1 , 12 , 15 , 26 , 38] và ar2 =[2 , 13 , 17 , 30 , 40]
Sau khi giao hai mảng ta có 1 mảng chung ar=[1 , 2 , 12, 13 , 15 , 17 , 26 , 30 , 38 , 40]
↝↝↝↝↝↝↝↝Median=(15+17)/2
Tư duy giải thuật 1: Ta dựa trên tư tưởng của giải thuật merge sort
Giải thuật merge sort: Giả sử một mảng số nguyên chưa có thứ tự. Ta sẽ xem các phần tử riêng lẻ hay một nhóm phần tử là một đường chạy ( một nhóm phần tử được gọi là 1 đường chạy nếu thỏa mãn an<an+1<...<an+x ).
Mục đích của giải thuật merge sort là làm giảm số đường chạy về một và mảng được xem sắp xếp xong.
Ta chia các đường chạy có trong một mảng làm 2 phần, sau đó so sánh và gộp 2 đường chạy tương ứng của 2 phần thành 1 đường chạy. Qúa trình trên lập lại nhiều lần, đến khi số đường chạy còn lại 1. DONE !.
Trở lại bài toán trên,ta thấy đó là bước lặp cuối cùng của thuật toán merge sort, ta đang có 2 đường chạy. Vậy chỉ cần so sánh các phần tương ứng của 2 mảng trên và ra được một danh sách phần tử giao giữa 2 mảng đã được sắp xếp !.
Tư duy lập trình 1: Bài toán này chỉ yêu cầu ta xác định median nên ta chỉ cần số cặp số so sánh bằng với kích thước n của mỗi mảng cộng thêm 1 là được.
Full Python code:
Time complexity: O(n)
Tư duy giải thuật 2: "Chia để trị" trung vị trong một mảng phần tử đã được sắp xếp thì ngoài mang ý nghĩa là vị trí đứng giữa và còn là vị trí giúp ta chia được danh sách thành 2 phần lớn và bé.
Vậy nếu như một mảng muốn chia thành 3 phần thì cần 2 trung vị ( trong trường hợp này thì dùng từ trung vị không đúng nhưng cứ tạm gọi là vậy ).
Ý tưởng của bài toán đã hình thành, quan sát hình sau:
Giả sử ta có 2 mảng sau ( đã được sắp xếp tăng dần):
ar1=[a1 , b1 , c1 , d1 , e1] và ar2 = [ a2 , b2 , c2 , d2 , e3]
Ta có media của mảng 1: m1=c1 và mảng 2: m2=c2
Nếu m2 > m1 thì rõ ràng a1 và b1 chắc chắn bé hơn c2 và cộng với việc cả 2 phần tử này theo đề bài đã nhỏ hơn c1 nên sẽ nằm phía ngoài cùng bên trái của mảng sau khi giao giữa 2 ar1 và ar2. Và hơn thế nữa d2 và e2 chắc chắn lớn hơn c1 và theo đề bài lớn hơn cả c2 nên chúng sẽ nằm ngoài cùng bên phải của mảng sau khi giao giữa hai mảng.
Vậy là rõ ràng median mà ta đang tìm kiếm sẽ phải phụ thuộc vào 2 mảng con sau:[d1,e1] và [a2,b2]
khi kích thước mỗi con là 2 thì ta dừng việc "chia"
median cần tìm dễ dàng tìm thấy được =(min(ar1[0],ar2[0] + max(ar1[1],ar2[1])) /2
Lý luận tương tự cho trường hợp m1>m2
Nội dung giải thuật:
1.
Tính toán m1 và m2
2.
Nếu m1 và m2 bằng nhau à return m1 or m2
3.
Nếu m1 lớn hơn m2, median được tìm thấy dựa vào
2 mảng con sau:
·
Từ phần tử đầu tiên của ar1 đến m1
·
Từ m2 đến phần tử cuối cùng của ar2
4.
Nếu m2 lớn hơn m1, median được tìm thấy dựa vào
2 mảng con sau:
·
Từ m1 đến phần tử cuối cùng của mảng ar1
·
Từ phần tử đầu tiên của ar2 đến m2
5.
Nhắc lại quá trình trên cho đến khi kích thước của
2 mảng thành 2
6.
Nếu kích thước của 2 mảng là 2 thì áp dụng công
thức sau để tìm median:
Median=(max(ar1[0],ar2[0]) +
min(ar1[1]+ar2[1]))/2
Tư duy lập trình: dùng đệ quy để ứng dụng giải thuật trên !
C code:
Time complexity: O(logn)
Kết luận: Rõ ràng chi phí dành cho giải thuật 2 là ít hơn là giải thuật 1. Tuy nhiên giải thuật 2 implement phức tạp hơn giải thuật 1.
The end !
Mong nhận sự đóng góp của các bạn.
Edit by me _BNT
Tham khảo đề bài: geeksforgeeks
Không có nhận xét nào:
Đăng nhận xét