leetcode解题: Majority Element (169)

发表于 | 分类于

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

解法1：抵消的思路，O(N) Time + O(1) Space

运用抵消的思路，如果有多余半数的一个数字，那么如果我们俩俩抵消不一样的数字，最后剩下来的一定是最多的那个数字。
抵消的实现用一个计数器，当两个数字不一样的时候，计数器减少1，如果归0了则更改被选答案到当前选定的数字。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        int count = 1; int result = nums[0];
        for (int num: nums) {
            if (num == result) ++count;
            else count--;
            if (count == 0) {
                result = num;
                ++count;
            }
        }
        return result;
    }
};

Java

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
class Solution {
    public int majorityElement(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int res = nums[0], count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == res) {
                count++;
            } else {
                count--;
                if (count == 0) {
                    res = nums[i];
                    count = 1;
                }
            }
        }
        return res;
    }
}

解法2：排序 O(NlogN)

因为多数元素个数超过半数，那么排序之后，当中的元素一定是最多的元素。
这个方法也能过OA
C++

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};