卖萌的弱渣

I am stupid, I am hungry.

Majority Number

Majority Number Show result

Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.

Example

Given [1, 1, 1, 1, 2, 2, 2], return 1

Challenge

O(n) time and O(1) extra space

Solution

  • The challenge require Moore’s Voting Algorithm to solve
  • Hash_map solution consume O(n), O(n)
(Majority-Number.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    """
    @param nums: A list of integers
    @return: The majority number
    """
    def majorityNumber(self, nums):
        # write your code here

        hash_map = dict()

        for i in nums:
            if hash_map.has_key(i):
                hash_map[i] += 1
            else:
                hash_map[i] = 1

        max = 0
        result = 0
        for i in nums:
            if hash_map[i] > max:
                max = hash_map[i]
                result = i
        return result