Skip to content

17.10. Find Majority Element

Description

A majority element is an element that makes up more than half of the items in an array. Given a positive integers array, find the majority element. If there is no majority element, return -1. Do this in O(N) time and O(1) space.

Example 1: 


Input: [1,2,5,9,5,9,5,5,5]

Output: 5

 

Example 2: 


Input: [3,2]

Output: -1

 

Example 3: 


Input: [2,2,1,1,1,2,2]

Output: 2

Solutions

Solution 1

1
2
3
4
5
6
7
8
9
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cnt = m = 0
        for v in nums:
            if cnt == 0:
                m, cnt = v, 1
            else:
                cnt += 1 if m == v else -1
        return m if nums.count(m) > len(nums) // 2 else -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int majorityElement(int[] nums) {
        int cnt = 0, m = 0;
        for (int v : nums) {
            if (cnt == 0) {
                m = v;
                cnt = 1;
            } else {
                cnt += (m == v ? 1 : -1);
            }
        }
        cnt = 0;
        for (int v : nums) {
            if (m == v) {
                ++cnt;
            }
        }
        return cnt > nums.length / 2 ? m : -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cnt = 0, m = 0;
        for (int& v : nums) {
            if (cnt == 0) {
                m = v;
                cnt = 1;
            } else
                cnt += (m == v ? 1 : -1);
        }
        cnt = count(nums.begin(), nums.end(), m);
        return cnt > nums.size() / 2 ? m : -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func majorityElement(nums []int) int {
    cnt, m := 0, 0
    for _, v := range nums {
        if cnt == 0 {
            m, cnt = v, 1
        } else {
            if m == v {
                cnt++
            } else {
                cnt--
            }
        }
    }
    cnt = 0
    for _, v := range nums {
        if m == v {
            cnt++
        }
    }
    if cnt > len(nums)/2 {
        return m
    }
    return -1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
    let cnt = 0,
        m = 0;
    for (const v of nums) {
        if (cnt == 0) {
            m = v;
            cnt = 1;
        } else {
            cnt += m == v ? 1 : -1;
        }
    }
    cnt = 0;
    for (const v of nums) {
        if (m == v) {
            ++cnt;
        }
    }
    return cnt > nums.length / 2 ? m : -1;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public int MajorityElement(int[] nums) {
        int cnt = 0, m = 0;
        foreach (int v in nums)
        {
            if (cnt == 0)
            {
                m = v;
                cnt = 1;
            }
            else
            {
                cnt += m == v ? 1 : -1;
            }
        }
        cnt = 0;
        foreach (int v in nums)
        {
            if (m == v)
            {
                ++cnt;
            }
        }
        return cnt > nums.Length / 2 ? m : -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    func majorityElement(_ nums: [Int]) -> Int {
        var count = 0
        var candidate: Int?

        for num in nums {
            if count == 0 {
                candidate = num
                count = 1
            } else if let candidate = candidate, candidate == num {
                count += 1
            } else {
                count -= 1
            }
        }

        count = 0
        if let candidate = candidate {
            for num in nums {
                if num == candidate {
                    count += 1
                }
            }
            if count > nums.count / 2 {
                return candidate
            }
        }

        return -1
    }
}

Comments