Tối ưu trộn 1 mảng giảm và 1 mảng tăng thành 1 mảng giảm trong thời gian ngắn nhất

nhk · July 2, 2021, 4:48pm

Gỉa sử ta có mảng a có m phần tử được sắp xếp giảm dần, mảng b có n phần tử
được sắp xếp tăng dần. Hãy viết chương trình trộn 2 mảng a và b lại thành mảng có m+n phần tử
được sắp xếp giảm dần, sao cho chương trình có thời gian chạy thấp nhất có thể. Hãy tính độ
phức tạp của chương trình được đề xuất.

Mọi người giúp em với ạ.
Em nghĩ mãi mà chưa tìm được lời giải ạ!

rogp10 · July 2, 2021, 10:22pm

Mảng tăng mà đọc ngược sẽ thành mảng giảm

HanQuaNhanh · July 2, 2021, 10:34pm

Nghe căng phết nhỉ? Bó tay

HR16 · July 3, 2021, 12:03am

Gợi ý 1:

Gợi ý 2: Chỗ nào còn trống thì cứ việc chèn vô

Gợi ý 3

Để ý kĩ ở chỗ “đã được sắp xếp”. Thuật toán tối ưu nhất có độ phức tạp tuyết tính O(n + m)

SITUVN.gcd · July 3, 2021, 12:31am

Merge Sort.
Phần Sort đã xong, giờ thì làm phần Merge thôi. B tăng dần, chạy ngược lại thì thành giảm dần.

vanduong · July 4, 2021, 5:38pm

Thực ra chỉ là sắp xếp chọn thôi. Mỗi lần duyệt sẽ chọn ra 1 giá trị lớn nhất của cả 2 mảng và đặt vào mảng đích.
Tạo 1 mảng C độ dài m+n, và 2 biến index cho 2 mảng ban đầu là indexA = 0 và indexB = length - 1 ( vì nó là mảng tăng nên duyệt từ cuối lên đầu để thành mảng giảm).
Duyệt mảng C, so sánh giá trị A[indexA] và B[indexB] xem cái nào lớn hơn thì đặt vào C. Tăng index vừa được đẩy vào C. -> Cứ thế duyệt tiếp để luôn chọn được ra giá trị lớn nhất còn lại trong 2 mảng đặt vào C.
-> Độ phức tạp O(m+n)