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.

题目意思

找到一个数组中出现次数最多的数字

解答

方法一

利用C++ 中的map map 中可以存储键值对。所以将数组的元素存到map中 存储形式<vector<i>,count> 然后遍历map 找出最大值为止。

int majorityElement(vector<int>& nums) { map<int, int> im; for (auto e : nums) ++im[e]; int temp = im.begin()->second; int mE=im.begin()->first; for (auto e : im) if (e.second > temp){ temp = e.second; mE = e.first; } return mE; } }

方法二

出现最多的元素，根据题目知道一定超过了一半，我们可以遍历数组，当遇到相同数字时计数器就加一，当不同的时候就减一，如果计数器等于0了，那么这个数字肯定不是出现最多的。（因为出现最多的元素的次数超过了一半）

int majorityElement(vector<int>& nums) { int mE = nums[0]; vector<int>::size_type index = 0; int count = 0; for (;index<nums.size();index++) { if (count == 0 || mE == nums[index]) { mE = nums[index]; count++; } else count--; } return mE; }

总结

方法一，因为要遍历两次，所以时间复杂度比方法二大