【LeetCode】Majority Element（求主元素）

说明

这道题出现在了王道的《2019数据结构考研复习指导》的18页，LeetCode中也有这道题。题目大意是:给定一个长度为n的数组，我们定义"主元素"为数组中出现次数超过⌊n/2⌋的元素。

Description

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.

Example 1:

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

Example 2:

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

解析

设数组为nums, 主元素为data，主元素出现的次数为count;

1. 假设第一个元素可能成为主元素，则data = nums[0]，count=1
2. i = i + 1， 比较nums[i]是否等于当前的主元素data，如果相等则说明data出现的次数又多了一次，count = count + 1；如果不相等，则让count = count - 1
3. 如果count为0， 让data = nums[i]（假设为主元素）
4. 重复2、3步，直到遍历完所有的元素。
5. 如果count > 0，遍历所有的元素，统计出值等于data的元素的个数c，如果元素个数c大于 > n/2，则说明data是该数组的主元素。

此算法的基本思想就是如果某个元素是数组nums的主元素，则它出现的次数一定大于数组元素的一半，且一定是最后一个重置data的元素。
时间复杂度: O(n)，空间复杂度: O(1)

C++实现

#include <iostream>
#include <vector>
using namespace std;
int majorityElement(vector<int> &nums);
int main()
{
    int n;
    vector<int> nums;
    cin >> n;   // 第一行输入n(元素的总数)
    while (n--) // 依次读取n个数字
    {
        int t;
        cin >> t;
        nums.push_back(t);
    }
    int element = majorityElement(nums);
    cout << element;
    return 0;
}
int majorityElement(vector<int> &nums)
{
    if (nums.empty())
        return -1;
    if (nums.size() == 1)
        return nums[0];
    int count = 1;
    int data = nums[0];
    for (int i = 1; i < nums.size(); ++i)
    {
        if (data == nums[i])
            count++;
        else
            count--;
        if (count == 0)
        {
            data = nums[i];
            count = 1;
        }
    }
    int c = 0;
    if (count > 0)
    {
        for (int i = 0; i < nums.size(); ++i)
        {
            if (data == nums[i])
                c++;
        }
    }
    if (c > nums.size() / 2)
        return data;
    else
        return -1;
}

本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明: 作者staneyffer，首发于我的博客，原文链接: https://chengfy.com/post/7