# My C Solution, O(n) time, O(1) space averagely

• ``````int* majorityElement(int* nums, int numsSize, int* returnSize)
{
int num1 = 0, cnt1 = 0, num2 = 0, cnt2 = 0, i = 0;
*returnSize = 0;

for (i = 0; i < numsSize; i++)
{
if (cnt1 == 0) num1 = nums[i];
else if (cnt2 == 0 && num1 != nums[i]) num2 = nums[i];

if (nums[i] == num1)
cnt1++;
else if (nums[i] == num2)
cnt2++;
else
cnt1--, cnt2--;
}
cnt1 = cnt2 = 0;
for (i = 0; i < numsSize; i++)
{
if (nums[i] == num1) cnt1++;
else if (nums[i] == num2) cnt2++;
}
if (cnt1 > numsSize / 3)
(*returnSize)++;
else
num1 = num2;
if (cnt2 > numsSize / 3)
(*returnSize)++;

if (*returnSize == 0) return NULL;
int *returnArray = (int *)malloc(sizeof(int) * (*returnSize));
if (returnArray != NULL)
{
returnArray[0] = num1;
if (*returnSize > 1) returnArray[1] = num2;
}

return returnArray;
}``````

• Moore voting algorithm

• This solution will produce the wrong answer for the following test case:
[1,2,2,3,2,1,1,3]
Should return 1 and 2 instead of just 1.

You need to check whether num equals to num1 and num equals to num2, respectively.
Also initializing num1/num2 is tricky. If num1 and num2 are initialized to a value that exists in the array, then the algorithm doesn't work.

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