LeetCode 169 Majority Element（主要元素）（vector、map）

LeetCode 169 Majority Element（主要元素）（vector、map）

翻譯

給定一個長度為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-1
2-2
3-5
4-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;
    }
};