2015.1.23 17:46
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:
This is FAQ, you know. See the code below.
Total time complexity is O(n). Space complexity is O(1).
Accepted code:
1 // 1AC, old 2 class Solution { 3 public: 4 int majorityElement(vector<int> &num) { 5 int val, cnt; 6 int n, i; 7 8 n = (int)num.size(); 9 val = num[0]; 10 cnt = 1; 11 12 for (i = 1; i < n; ++i) { 13 if (val == num[i]) { 14 ++cnt; 15 } else if (cnt > 1) { 16 --cnt; 17 } else { 18 val = num[i]; 19 cnt = 1; 20 } 21 } 22 23 return val; 24 } 25 };
原文：http://www.cnblogs.com/zhuli19901106/p/4244772.html