Bài cần làm: Cho 1 mảng có n phần tử, tìm số lớn thứ hai DUY NHẤT, nếu không có thì trả về -1, độ phức tạp cần là O(n)!
Lời giải 1: Đơn giản nhất, dùng sort! Viết luôn, khỏi giải thích nhé =))
Code source:
Tuy nhiên, dễ thấy đây là lời giải chưa tối ưu
Phức tạp thời gian: O(n*log(n))!
Lời giải 2: Tìm số lớn nhất rồi lại scan thêm lần nữa để tìm số nhỏ thứ nhì!
Ủa, nghe cứ sao sao ý nhỉ =)))
Thôi, đùa tí, code ở dưới này:
Có lẽ, lời giải này chưa đủ tối ưu nhỉ, cùng tính độ phức tạp nhé!
Mình đang đi qua mảng 2 lần, nên độ phức tạp là O(2n)! Chưa đủ nhỉ, phải tìm cách nữa thôi
Cách 3: Đi qua mảng 1 lần rồi cập nhật 2 biến lớn thứ nhất và nhì luôn!
Bằng cách này thì sẽ không bị lặp lại thêm 1 lần đi qua mảng nên sẽ tối ưu hơn, 2 lần lận so với cách 2 luôn nhé!
Tối ưu nhất luôn nhé!
Hmm, độ phức tạp O(n) rồi!
Yay, làm được rồi!
Mong bạn học được thêm nhiều qua bài đọc này, cảm ơn vì đã đọc nhé!
Bình luận
Vẫn 2N mà... bro chưa xét hằng số rồi
Mình tưởng độ phức tạp là O(n) chứ nhỉ? Mình duyệt qua mảng chỉ 1 lần thôi mà, và thực hiện của 2 công việc trong 1 lúc vơi cập nhật các biến liên tục mà. Bạn thử lên mấy trang tính toán độ phức tạp ý, nó tính ra O(n) mà.
N hay 2N khác gì vậy bạn
Giống nhau mà =)
Mình ko chuyên về độ phức tạp lắm, hay lên mấy trang web để xem th
Mong bạn thông cảm
bài toán 3.6: cho 1 hàm N* -> N*, tìm giá trị lớn thứ hai của hàm trong [L;R) trong o(R-L)
bài toán 3.67: cho 1 mảng, tìm giá trị lớn thứ k với cập nhật trong o(log(n))
bạn có thể làm thử 2 bài toán trên. Lời giải cực kì cơ bản và phù hợp với HS lớp 9...