LeetCode169. Majority Element

题目描述:

给定一个长度为n的数组，找到出现次数最多的元素。该元素出现的次数超过[n/2]次。你可以假设数组非空并且多数元素总是存在数组中。

Example1

Input: [3,2,3]
Output: 3

Example2

Input: [2,2,1,1,1,2,2]
Output: 2

C++输入格式

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        
    }
};

范例一

第一种方式是使用C++的哈希表

//unordered_map 是C++哈希表的实现模板
//unordered_map中不允许有重复的key，因此如果key存在，则count返回1，如果不存在则count返回0
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counter;
        cout<<"每个元素随遍历过程出现的次数:"<<endl;
        for (int num : nums) {
            
            cout<<counter[num]<<endl;
            if (++counter[num] > nums.size() / 2) {
                return num;
            }
        }
        return 0;
    }
};

main()

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    vector<int> vec;
    int m;
    int a[10]={2,1,2,3,2,2};
    for(i=0;i<6;i++)
    {
       vec.push_back(a[i]);
    }

    vector<int>::iterator pos;
    //声明一个迭代器，来访问vector容器。作用:遍历或指向vector容器的元素 
    cout<<"输入数组:";
    for(pos = vec.begin();pos!=vec.end();pos++)
    {
        cout<<*pos<<" ";
    } 
    cout<<endl;
    Solution sol;
    m = sol.majorityElement(vec);
    cout<<m<<endl;
    return 0;
}

测试样例输出

image.png

范例二

第一种方式是使用C++自带的排序算法，因为该数组中肯定存在次数大于[n/2]的元素，所以我们只需对一半数据进行排序取出中间位对应的元素就一定是我们想要的元素。

#include <iostream>
#include <vector>
#include <algorithm>  
using namespace std;
//unordered_map 是C++哈希表的实现模板
//unordered_map中不允许有重复的key，因此如果key存在，则count返回1，如果不存在则count返回0
class Solution {
public:
     int majorityElement(vector<int>& nums) {
        nth_element(nums.begin(), nums.begin() + nums.size()/ 2, nums.end());
        return nums[nums.size() / 2];
    }
};

c++中nth_element()函数对给定范围[first,last)内的元素进行重新布置。通过调用nth_element(start, start+n, end) 方法可以使第n/2大元素处于第n/2位置(从0开始，其位置是下标为n/2的元素)，并且比这个元素小的元素都排在这个元素之前，比这个元素大的元素都排在这个元素之后，但不能保证他们有序。
测试用例

测试结果

范例三

采用摩尔投票法

class Solution {
public:
     int majorityElement(vector<int>& nums) {
        int counter = 0, majority;
        for (int num : nums) {
            if (!counter) {
                majority = num;
            }
            counter += num == majority ? 1 : -1;
            cout<<counter<<endl;
        }
        return majority;
    }
};

对每个元素进行遍历，把每个元素当成majority，若在后面还遇到相同的元素就加一否则减一，最后输出次数最多的元素。majority存放的始终都是次数较多的元素。
输出每次变化前后的counter，并对测试结果进行截图

image.png

测试使用在线编译器运行代码