【20190326】【每天一道算法題】求衆數（分治算法）

問題：

給定一個大小為 n 的數組，找到其中的衆數。衆數是指在數組中出現次數大于 

⌊ n/2 ⌋

 的元素。

你可以假設數組是非空的，并且給定的數組總是存在衆數。

我的思路及代碼：

/* 思路：分治算法
 *
 * 邏輯：Step1：去重，将不重複的元素放在另外一個數組（nums_tmp）中；
 *       Step2：周遊原始數組，算出nums_tmp中各個元素在nums出現的次數，如果滿足衆數的條件，那麼
 *              傳回該元素
*/
int majorityElement(int* nums, int numsSize) 
{
    int *p1 = nums;
    int *p2 = NULL;
    int j=1;
    int nums_tmp[128] = {0};
    nums_tmp[0] = nums[0];
    for(int i = 0; i < numsSize-1; i++)
    {
        p2 = p1 + i;
        while(*p2 != *p1)
        {
            nums_tmp[j++] = *p2;
        }    
    }
    int len2 = sizeof(nums_tmp)/sizeof(nums_tmp[0]);
    int Num[50] = {0};
    for(int i =0; i < len2; i++)
    {
        Num[i]++;
        for(int j = 0; j < numsSize; j++)
        {
            while(nums[j] == nums_tmp[i])
                Num[i]++;
            if(Num[i] > numsSize/2)
                return nums_tmp[i];
        }
    }
}