转载

【LeetCode】169. Majority Element

问题描述

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.

Credits:

Special thanks to @ts for adding this problem and creating all test cases.

找出数组中个数超过了n/2个的元素。

注意：测试用例中数组不为空并且一定会出现Majority元素

思路

Hash表计数法：用一个Hash表记录每个元素出现的次数
Moore voting algorithm：记录元素elem，计数器counter，遍历数组，如果counter为0，则elem为当前元素；如果counter不为0，若elem==当前元素，counter++，若elem!=当前元素，counter--，最终的elem一定输Majority元素。因为一定会出现Majority元素，所以它的元素个数是大于n/2的，假设有k个，其余元素有m个，肯定有 k>m，所以最终计数下来，剩下的那个肯定是Majority元素

代码

1 Hash表计数法

class Solution {  
public:

    int majorityElement(vector<int>& nums) {
        map<int, int> counts;
        for (int i = 0; i<nums.size(); i++) {
            if (counts.find(nums[i]) == counts.end()) {
                counts[nums[i]] = 0;
            }
            counts[nums[i]]++;
            if (counts[nums[i]]>nums.size() / 2) {
                return nums[i];
            }
        }
        return 0;
    }
}

2 Moore voting algorithm

class Solution {  
public:

    int majorityElement(vector<int>& nums) {
        int count = 0;
        int elem = 0;
        for (int i = 0; i<nums.size(); i++) {
            if (count == 0) {
                elem = nums[i];
                count++;
            }
            else {
                if (elem == nums[i]) {
                    count++;
                }
                else {
                    count--;
                }
            }
        }
        return elem;
    }
}

转载请注明出处

：

http://www.zgljl2012.com/leetcode-169-majority-element/

原文 http://www.zgljl2012.com/leetcode-169-majority-element/

正文到此结束