Editorial for Dãy chẵn lẻ cân bằng
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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.
Comments