---
title: 'LeetCode 169. Majority Element'
disqus: hackmd
---

# LeetCode 169. Majority Element

## Description

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

## Example

Input: nums = [3,2,3]
Output: 3

Input: nums = [2,2,1,1,1,2,2]
Output: 2

## Constraints

n == nums.length
1 <= n <= 5 * 10^4^
-10^9^ <= nums[i] <= 10^9^

## Answer
方法1
此題可以先排序再依序計算，若有值相同的就cnt++，且每次都檢查cnt滿足了沒。此法可解大部分況，但若test case太大就會做很久。

//2021_11_23
void mysort(int *nums,int left,int right);

int majorityElement(int* nums, int numsSize) {
    if(numsSize < 2){return *nums;}
    mysort(nums, 0, numsSize - 1);
    int i = 0, flag = 1, cnt = 1;
    while(flag && i < numsSize){
        i++;
        if(nums[i - 1] == nums[i]){cnt++;}
        else{cnt = 1;}
        if(cnt > numsSize/2 ){flag = 0;}
    }
    return nums[i];
}

void mysort(int *nums,int left,int right){
    if(left<right){
        int L = left+1,R = right,pivot = left;
        while(L<R){
            while(L<right && nums[L]<=nums[pivot]){L++;}
            while(R>left && nums[R]>nums[pivot]){R--;}
            if(L<R){
                int temp = nums[L];
                nums[L] = nums[R];
                nums[R] = temp;
            }
        }
        if(nums[R]<nums[pivot]){
            int temp1 = nums[R];
                nums[R] = nums[pivot];
                nums[pivot] = temp1;
        }
        mysort(nums,left,R-1);
        mysort(nums,R+1,right);
    }
}

方法2
因為ans的個數大於numsSize/2，所以cnt再怎麼++ --，ans都一定還是會取到正確值，若最後一位是答案，則ans就會更新為最後一位，若最後一位不是答案，表示ans已存著正確答案，則直接return ans即可，以上的重點都是ans的個數大於numsSize/2。

//2021_11_23
int majorityElement(int* nums, int numsSize) {
    if(numsSize < 2){return *nums;}
    int i = 0, ans = 0, cnt = 0;
    for(i = 0; i < numsSize; i++){
        if(cnt == 0){ans = nums[i];}
        if(ans == nums[i]){cnt++;}
        else{cnt--;}
    }
    return ans;
}

## Link
https://leetcode.com/problems/majority-element/
###### tags: `Leetcode`