[Array]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.

方法：充分利用主元素出现次数大于⌊ n/2 ⌋ 这个条件，根据这个条件，顺序遍历整个数组，我们可以为一个元素设置一个计数器，假设以第一个元素为例，为第一个元素设置一个count=1，表明出现过一次，然后遍历第二个元素，当第二个元素与第一个元素相等时，count++,表明出现过两次，当第二个元素与第一个元素不等时，count- -,当遍历第三个元素时如果发现count=0,则为第三个元素设置一个计数器，依次类推。
时间复杂度：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;} };

转载于:https://www.cnblogs.com/GoFly/p/5751064.html

总结

以上是生活随笔为你收集整理的[Array]Majority Element的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。