Majority Number II

Given an array of integers, the majority number is the number that occursmore than 1/3of the size of the array.

Find it.

Solution and Analysis:

• two passes on the array. first time to pick out top two numbers, second time to compare

• adding count is also tricky to do in order

Python solution

class Solution:
    """
    @param: nums: a list of integers
    @return: The majority number that occurs more than 1/3
    """
    def majorityNumber(self, nums):
        # write your code here

        num1 = nums[0]
        count1 = 1
        start = 1
        while nums[start] == num1:
            count1 += 1
            start += 1
        num2 = nums[start]
        count2 = 1

        for i in range(start+1, len(nums)):
            if nums[i] == num1:
                count1 += 1
            elif nums[i] == num2:
                count2 += 1
            elif nums[i] != num1 and nums[i] != num2:
                if count1 == 0:
                    num1 = nums[i]
                    count1 = 1
                elif count2 == 0:
                    num2 = nums[i]
                    count2 = 1
                else:
                    count1 -= 1
                    count2 -= 1
        count1 = 0
        count2 = 0
        for num in nums:
            if num1 == num:
                count1 += 1
            elif num2 == num:
                count2 += 1

        if count1 > count2:
            return num1
        else:
            return num2

Complexity:

time: O(n)

space: O(1)