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.

Credits:

Special thanks to  for adding this problem and creating all test cases.

 

int majorityElement(int* nums, int numsSize) {      if(numsSize == 0||numsSize == 1)          return *nums;            int x = majorityElement(nums,numsSize / 2);      int y = majorityElement(nums + numsSize / 2,numsSize - numsSize / 2);            if(x == y)          return x;            else      {          int countX = 0;          int countY = 0;                    for(int i = 0;i < numsSize;i++)          {              if(*(nums + i) == x)                  countX++;                            else if(*(nums + i) == y)                  countY++;          }                    return countX > countY ? x : y;      }        }