LeetCode Weekly Contest 149
問題文
省略
省略
C++に変換後のコードはこちら
#define main dummy_main
{}
#undef main
int gcnt[20001];
class MajorityChecker {
public:
int N;
vector<int> A;
int M, B;
int mval[100];
map<int,int> mp[100];
MajorityChecker(vector<int>& arr) {
int i, j, k, a, b;
int mxind, mxval;
A = arr;
N = A.size();
M = 300;
B = N /+ M;
rep(i,20001) gcnt[i] = 0;
rep(k,B){
a = M*k;
b = min(M*(k+1), N);
mxval = 0;
rep(i,a,b){
gcnt[A[i]]++;
if(mxval < gcnt[A[i]]){
mxval = gcnt[A[i]];
mxind = A[i];
}
}
mval[k] = mxind;
rep(i,a,b) mp[k][A[i]] = gcnt[A[i]];
rep(i,a,b) gcnt[A[i]]--;
}
}
int query(int a, int b, int t) {
int i, ii, x, aa, bb;
int val, cnt;
vector<int> koho;
b++;
if(b-a < 1000){
cnt = 0;
rep(i,a,b){
if(cnt==0){
val = A[i];
cnt++;
} else if(val==A[i]){
cnt++;
} else {
cnt--;
}
}
if(cnt==0) return -1;
cnt = 0;
rep(i,a,b) if(val==A[i]) cnt++;
if(cnt >= t) return val;
return -1;
}
aa = (a /+ M) * M;
bb = (b / M) * M;
if(a != aa){
i = query(a,aa-1,0);
if(i>=0) koho.push_back(i);
}
if(b != bb){
i = query(bb,b-1,0);
if(i>=0) koho.push_back(i);
}
rep(i,aa/M,bb/M) koho.push_back(mval[i]);
sort(koho.begin(), koho.end());
rep(ii,koho.size()){
if(ii>0 && koho[ii]==koho[ii-1]) continue;
x = koho[ii];
cnt = 0;
rep(i,a,aa) if(A[i]==x) cnt++;
rep(i,aa/M,bb/M) if(mp[i].count(x)) cnt += mp[i][x];
rep(i,bb,b) if(A[i]==x) cnt++;
if(cnt >= t) return x;
}
return -1;
}
};
Current time: 2024年03月29日17時07分36秒
Last modified: 2019年08月18日05時25分14秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る
Logged in as: unknown user (not login)