首页 > 程序开发 > 软件开发 > C++ >

[C++]LeetCode: 50 Majority Element

2014-12-23

题目: 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

题目:

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.

找出数组中出现次数超过数组长度一半的值。


Solution:

  1. Runtime: O(n2)— Brute force solution: Check each element if it is the majority element.
  2. Runtime: O(n), Space: O(n)— Hash table: Maintain a hash table of the counts of each element, then find the most common one.
    1. Runtime: O(n log n)— Divide and conquer: Divide the array into two halves, then find the majority element A in the first half and the majority element B in the second half. The global majority element must either be A or B. If A == B, then it automatically becomes the global majority element. If not, then both A and B are the candidates for the majority element, and it is suffice to check the count of occurrences for at most two candidates. The runtime complexity, T(n) = T(n/2) + 2n = O(n logn).
    2. Runtime: O(n) —Moore voting algorithm: We maintain a current candidate and a counter initialized to 0. As we iterate the array, we look at the current element x:
      1. If the counter is 0, we set the current candidate to x and the counter to 1.
      2. If the counter is not 0, we increment or decrement the counter based on whether x is the current candidate. After one pass, the current candidate is the majority element. Runtime complexity = O(n)
        Moore Voting Algorithm: 该算法要求目标数组存在majority元素(大于n/2),否则需要检验。 算法演示 here. 思路解析: 1. 初始化majorityIndex,并且维护其对应count; 2. 遍历数组,如果下一个元素和当前候选元素相同,count加1,否则count减1; 3. 如果count为0时,则更改候选元素,并且重置count为1; 4. 返回A[majorityIndex] 原理:如果majority元素存在(majority元素个数大于n/2,个数超过数组长度一半),那么无论它的各个元素位置是如何分布的,其count经过抵消和增加后,最后一定是大于等于1的。 如果不能保证majority存在,需要检验。 复杂度:O(N) Attention: 循环时从i = 1开始,从下一个元素开始,因为count已经置1. AC Code:
        class Solution {
        public:
            int majorityElement(vector &num) {
                //the majority element 存在并且唯一
                
                int majorityIndex = 0;
                for(int cnt = 1, i = 1; i < num.size(); i++)
                {
                    num[majorityIndex] == num[i] ? cnt++ : cnt--;
                    if(cnt == 0)
                    {
                        cnt = 1;
                        majorityIndex = i;
                    }
                }
                
                return num[majorityIndex];
            }
        };

        检验: /* Function to check if the candidate occurs more than n/2 times */ boolisMajority(inta[], intsize, intcand) { inti, count = 0; for(i = 0; i < size; i&#43;&#43;) if(a[i] == cand) count&#43;&#43;; if(count > size/2) return1; else return0; }







相关文章
最新文章
热点推荐