O(n) solution, quick-select.


  • 0
    R
        void swap(int* a,int* b)
    {int c=*a;
    *a=*b;
    *b=c;
    return;}
    
    int majorityElement(int* nums, int numsSize) {
    	if (numsSize<=1)return *nums;else{
        int i=0,j=numsSize-2,count=0;
        int pivot=*(nums+numsSize-1);
        while(i<=j){
        if( *(nums+i)>=pivot)
        {if( *(nums+i)==pivot) count++;
        swap(nums+i,nums+j);
        j--;}
        else i++;}
        swap(nums+i,nums+numsSize-1);
        if(count>=numsSize/2) return pivot;
        else if(i>numsSize-i) return majorityElement(nums, i);
        else return majorityElement(nums+i, numsSize-i);
    }}
    

    The main idea is using quick-select to find the median, meanwhile including a counter to count the number of "==" comparisons we get. If the number of "==" comparisons exceeds half of the list's size, the pivot is the majority element.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.