程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [C++]LeetCode: 50 Majority Element

[C++]LeetCode: 50 Majority Element

編輯:C++入門知識

[C++]LeetCode: 50 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.

找出數組中出現次數超過數組長度一半的值。


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++) if(a[i] == cand) count++; if(count > size/2) return1; else return0; }







  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved