Hướng dẫn cho Dãy chẵn lẻ cân bằng
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Cách 1 (trâu): Độ phức tạp \(O(n^2 )\)
Với mỗi vị trí \(i\), đếm số lượng số chẵn, số lẻ ở hai phía TRÁI, PHẢI và so sánh
Cách 2: Độ phức tạp \(O(n)\)
Tạo hai vecto Left và Right là hai mảng cộng dồn lưu:
- \(Left[i]\) lưu tần suất số lẻ \((Left[i].first)\) và số chẵn \((Left[i].second)\) của dãy bên trái \(i\)
- \(Right[i]\) lưu tần suất số lẻ \((Right[i].first)\) và chẵn \((Right[i].second)\) của dãy bên phải \(i\)
- Nếu \(Left[i].fisrt=Right[i].first\) hoặc \(Left[i].second=Right[i].second\) thì \(i\) chính là vị trí cần tìm.
Bình luận