LeetCode Weekly Contest 149 4問目 - Online Majority Element In Subarray [1157]

Source

LeetCode Weekly Contest 149
問題文

問題概要

省略

解法

省略

cLayversion 20190818-1)のコード

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)

ログイン: