http://codility.com/demo/take-sample-test/equileader
一开始想到从左和右两边开始扫取众数,但求众数又要重新扫一遍,这样复杂度就是O(n^2)了。
此题的关键在于Equi-Leader必然是众数,否则不可能左边和右边都是众数。
所以先求出众数及其出现次数,再扫就行了。
// you can also use includes, for example: // #include <algorithm> int solution(vector<int> &A) { // write your code in C++98 int x = A[0]; int cnt = 0; for (int i = 1; i < A.size(); i++) { if (A[i] == x) { cnt++; } else if (cnt > 0) { cnt--; } else { cnt = 1; x = A[i]; } } int total = 0; for (int i = 0; i < A.size(); i++) { if (A[i] == x) total++; } if (total <= A.size() / 2) return 0; int ans = 0; int currentTotal = 0; for (int i = 0; i < A.size() - 1; i++) { if (A[i] == x) currentTotal++; if ((currentTotal > (i + 1) / 2) && ((total - currentTotal) > (A.size() - i - 1) / 2)) { ans++; } } return ans; }