数组中出现次数超过一半的数字

//方案一： O(N)? 不适合海量数据
int* maxK(int A[] , const int& n, const int& k){
  if(n<k||n<=0||k<=0||A==NULL) cerr<<"Invalid Input"<<endl;
  int* output = new int[k]();
  if(n==k){
         for(int i = 0; i < n; ++i)
            output[i]=A[i];
          return output;  
   }
  int r = partition(A,0,n);
  while(r!=k){
       if(r<k)
       r = partition(A,r+1,n);
       else 
       r = partition(A,0,r-1);
   } 
     for(int i = 0; i < n; ++i)
            output[i]=A[i];
       return output;  
}

int partition(int A[], int begin, int end){
　　--end;
   int p = A[end];
   while(true){
      while(A[begin]<p) ++begin;
      while(A[end]>p) --end;
      if(begin>=end) return begin;
      swap(A[begin],A[end]);
      ++begin;
      --end;
   }
}

multiset<int>* maxK(const vector<int> &data, const int& k){
        multiset<int,greater<int>> rst;
        vector<int>::const_iterator iter = data.begin();
        for(;iter!=data.end();++iter){
               if(rst.size()<=k)
                     rst.insert(*iter);
              else{
                 int maxData = *rst.begin();
                 if(maxData>*iter){
                      rst.erase(maxData);
                      rst.insert(*iter);
                   }
               }
        }
        return rst;
}