翻译

给定一个长度为n的数组，找出主要的元素。所谓主要的元素是指的出现次数超过⌊ n/2 ⌋次的元素。你可以假定这个数组是非空的，并且“主要元素”一定是存在的。

原文

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这东西，直接是所有序列中最长的。

1,2,2,3,3,3,3,3,4,4-->1-12-23-54-2

看到了键值对，想到了基本的map，还有些复杂的容器我就用的不太熟悉了……

在下面的代码这两个，我首先定义了element元素，然后用range-for从nums中便利所有的元素：

1）如果在map中找不到这个元素，就添加进去；2）如果找到了，将其出现的个数加上1。如果当前的长度大于最大的长度，则进行一些列操作，并将max设置为当前的n，以便于后面的返回。

调试之后发现还有nums长度为1的情况，于是在开头加上一个判断。

int majorityElement(vector
     
      & nums) {    if (nums.size() == 1) return nums[0];    map
      
        element;    int max = 0, maxLen = 0;    for (auto n : nums) {        if (element.find(n) == element.end()) {            element.insert(map
       
        ::value_type(n, 1));        }        else {            element[n] += 1;            if (element[n] >= maxLen) {                maxLen = element[n];                max = n;            }        }    }    return max;}
       
      
     

代码

class Solution {public:    int majorityElement(vector
     
      & nums) {        if (nums.size() == 1) return nums[0];        map
      
        element;        int max = 0, maxLen = 0;        for (auto n : nums) {            if (element.find(n) == element.end()) {                element.insert(map
       
        ::value_type(n, 1));            }            else {                element[n] += 1;                if (element[n] >= maxLen) {                    maxLen = element[n];                    max = n;                }            }        }        return max;    }};