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.

方法：充分利用主元素出現(xiàn)次數(shù)大于? n/2 ? 這個條件，根據(jù)這個條件，順序遍歷整個數(shù)組，我們可以為一個元素設置一個計數(shù)器，假設以第一個元素為例，為第一個元素設置一個count=1，表明出現(xiàn)過一次，然后遍歷第二個元素，當?shù)诙€元素與第一個元素相等時，count++,表明出現(xiàn)過兩次，當?shù)诙€元素與第一個元素不等時，count- -,當遍歷第三個元素時如果發(fā)現(xiàn)count=0,則為第三個元素設置一個計數(shù)器，依次類推。
時間復雜度：O（n）
空間復雜度：O（1）

class Solution { public:int majorityElement(vector<int>& nums) {int value = nums[0];int count = 1;for(int i=1;i<nums.size();i++){if(count==0)value = nums[i];if(nums[i]==value)count++;elsecount--;}return value;} };

轉(zhuǎn)載于:https://www.cnblogs.com/GoFly/p/5751064.html

總結(jié)

以上是生活随笔為你收集整理的[Array]Majority Element的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。