1. 算法思想:将序列A排序,取排序后中间元素k为ret值.m初值为0,然后向前查找值为ret的值,若有则m加一,向后同理,最后若m大于n/2,则返回ret,反之返回-1.

int Partition(int A[], int low, int high)
{
  int p = A[low];
  while(low < high)
  {
   while ( low < high && A[high] >= p) high--;
   A[low] = A[high];
   while ( low < high && A[low] <= p) low++;
   A[high] = A[low];
  }
  A[low] = p;
  return low;
}

void QuickSort(int A[], int low, int high){
  if (low < high){
      int pivot = Partition(A, low, high);
      QuickSort(A, low, pivot-1);
      QuickSort(A, pivot+1, high);
  }
}

int FindMainElem(int A[], int n)
{
Quick(A, 0, n-1);
int ret = A[(n-1)/2];
int m = 0;
int k = (n-1)/2;
while(A[k] == ret){
m++;
k--;
}
k = (n-1)/2 + 1;
while(A[k] == ret){
m++;
k++;
}
return m>n/2?m:-1;
}

三: 时间复杂度: O(nlog2n)

空间复杂度:O(log2n)