74.数组中超过出现次数超过一半的数字（数组）

题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。

 

思路：分治算法 两两一对 相同留下一个 不同扔掉 多出来的数字单独对比

/*74.数组中超过出现次数超过一半的数字（数组）题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。*///思路：分治算法 两两一对 相同留下一个 不同扔掉 多出来的数字单独对比#include 
     
      #include 
      
       int find(int * in, int len){    if(len == 0)    {        return 0;    }    if(len % 2 == 1) //奇数，加一轮全部比较    {        int i = 0;        int count = 0;        for(i = 0; i < len; i++)        {            if(in[i] == in[len - 1])                count++;        }        if(count > (len-1)/2)        {            return in[len - 1];        }    }    int * remain = (int *)malloc(len / 2 * sizeof(int)); //无法释放了..??    int remainlen = 0;    for(int i = 0; i < len; i+=2)    {        if(in[i] == in[i+1])        {            remain[remainlen++] = in[i];        }    }    return find(remain, remainlen);    }int main(){    int a[10] = {
   5,6,7,8,5,5,5,5,5,6};    int ans = find(a, 10);    return 0;}
      
     

 

我的代码有个大问题，自己开辟的内存无法释放。在网上看答案，发现其实不用写得这么麻烦的...

网上的思路：http://www.oschina.net/code/snippet_859732_22139

 每次取出两个不同的数，剩下的数字中重复出现的数字肯定比其他数字多，将规模缩小。如果每次删除两个不同的数，那么剩下的数字里最高频数出现的频率一样超过一半，不断重复这个过程，最后剩下的将全是同样的数字。时间复杂度是O(n)

int findmostappear(int *a,int len) {       int candidate=0,count=0;       for(int i=0;i