169. 多数元素

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

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

示例 1：

输入：[3,2,3]
输出：3

示例 2：

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

解法：抵消

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let count = 1;
    let temp = nums[0];
    for(let i=1;i<nums.length;i++){
        if(count == 0){
            temp = nums[i];
        }
        if(nums[i] == temp) count++;
        else count--;
    }
    return temp;
};

解法：快排

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let len = nums.length - 1;
    doSort(nums,0,len);
    return nums[Math.floor(nums.length/2)];
};

var doSort = function(nums,left,right){
    if(left>=right) return;
    let mid = patition(nums,left,right);
    doSort(nums,left,mid-1);
    doSort(nums,mid+1,right);
}

var patition = function(nums,left,right){
    let base = nums[left];
    let start = left+1;
    let end = right;
    while(start < end){
        while(start < end && nums[start] <= base) start++;
        if(start!=end){
            exchange(nums,start,end);
            end--;
        }
    }
    if(start == end && nums[end] > base) end--;
    if(end != left){
        exchange(nums,left,end);
    }
    return end;
}

var exchange = function(nums,left,right){
    let temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
}