多数元素算法(leetcode第169题)

题目描述：

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

 

示例 1：

输入：nums = [3,2,3]
输出：3
示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2
 

提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

算法：先排序

思路：

先排序，再对相邻数进行比较，记录次数，取最大次数的值

代码实现：

int cmp(const void *a,const void *b){
    return *(int *)a-*(int *)b;
}

int majorityElement(int* nums, int numsSize) {
    qsort(nums,numsSize,sizeof(int),cmp);
    int cnt=1;
    int i;
    int ret=nums[0];
    for(i=0;i<numsSize-1;i++){
        //超过半数
        if(cnt>numsSize/2) return ret;
        //未超过半数
        if(nums[i]!=nums[i+1]){//不等
            cnt=1;//计数归零
            ret=nums[i+1];//重设ret
        }
        else{//相等
            cnt++;
        }
    }
    return ret;
}

算法：抵消

思路：

抵消次数以达到更新比较值的目的

代码实现：

int majorityElement(int* nums, int numsSize) {
    int i=0;
    int most=nums[i];
    int j=1;
    //1 1 3 3 1 2 1 2 1 
    for( i=1;i<numsSize;i++){
        if(nums[i]==most) j++;
        else{
            if(j==0){
                most=nums[i];//重新开始比较
                j++;
            }
            else j--;//抵消次数(比较剩余元素)
        }
    }
    return most;//返回最多元素
}