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