LeetCode 169

Majority Element

Given an array of size n, find the majority element.
The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

 1 /*************************************************************************
 2     > File Name: LeetCode169.c
 3     > Author: Juntaran
 4     > Mail: Jacinthmail@gmail.com
 5     > Created Time: Tue 10 May 2016 02:40:25 PM CST
 6  ************************************************************************/
 7  
 8 /*************************************************************************
 9 
10     Majority Element
11     
12     Given an array of size n, find the majority element. 
13     The majority element is the element that appears more than ⌊ n/2 ⌋ times.
14 
15     You may assume that the array is non-empty and the majority element always exist in the array.
16 
17  ************************************************************************/
18 
19 #include<stdio.h>
20 
21 int majorityElement( int* nums, int numsSize )
22 {
23     int ret = nums[0];
24     int count = 1;
25     
26     int i;
27     for( i=1; i<numsSize; i++ )
28     {
29         if( ret == nums[i] )
30         {
31             count ++;
32         }
33         else
34         {
35             count --;
36         }
37         if( count == 0 )
38         {
39             ret = nums[i];
40             count ++;
41         }
42     }
43     return ret;
44 }
45 
46 int main()
47 {
48     int nums[] = {3,2,3};
49     int numsSize = 3;
50 
51     int ret = majorityElement( nums, numsSize );
52     printf("%d
", ret);
53 
54     return 0;
55 }