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


  • 2
    V
    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;
    }

  • 0
    V

    Moore voting algorithm


  • 0
    J

    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.


Log in to reply
 

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