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

解法一：

int num(int *arr, int n)
{
if(arr==NULL||n<=0)
return 0;
//找数组中最大的元素max
int max=arr[0];
for(int i=1;i<n;i++)
  {
if(arr[i]>=max)
max=arr[i];
  }
//重新定义一个大小为max+1的数组arr1
int arr1[max+1];
//统计所给数组每个元素出现的次数，存放在数组arr1中
for(int i=0;i<n;i++)
  {
for(int j=0;j<max+1;j++)
  {
if(arr[i]==j)
    {
        arr1[j]++;
    }
  }
}
//找出出现次数超过数组长度一般的元素
for(int k=0;k<max+1;k++)
{
if(arr1[k]>(n/2))
return k;
}
}

解法二：：排序后数组中的中位数一定是出现次数超过数组长度一半的数字

    int MoreThanHalfNum_Solution(vector<int> numbers) {
if(numbers.size()==0)
return 0;
//对所给数组元素进行排序
        sort(numbers.begin(),numbers.end());
//找到排序后数组元素的中位数num
int num=numbers[numbers.size()/2];
//定义一个计数器
int count=0;
//统计中位数出现的次数
for(int i=0;i<numbers.size();i++)
            {
if(numbers[i]==num)
                count++;
        }
//如果中位数出现次数的2倍大于数组长度，说明已找到
if(count*2>numbers.size())
return num;      
return 0;
    }