Majority Element

2019-11-06 07:24:31

字体：大中小

来源：转载

供稿：网友

Leetcode-Algorithm-Divide and Conquer-169

题目：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的数组，找到数组元素中的绝对众数，绝对众数也就是出现次数大于等于n/2次的元素。–假定数组非空且绝对众数必定存在。）

题解：

方法1：（运用c++中map容器的特性）在c++中，map容器能够存储键值对。因此，我们可以把元素看成键（key），把每个元素的数目看成值（value），由于map容器中key不能重复，因此对于重复元素，我们可以用value进行计数。最后看哪个元素的计数大于n/2。

代码：

int majorityElement(vector<int>& nums) { if (nums.size() == 0) return -1; map<int, int> count; for (vector<int>::size_type ix = 0; ix < nums.size(); ++ix) if (++count[nums[ix]] > nums.size()/2) return nums[ix]; return -1;}

方法2：（运用排序以及绝对众数的特征）由于绝对众数的个数大于数组大小的一半，因此，当数组排序后，位于数组中央的元素必定是绝对众数。

代码：

int majorityElement(vector<int>& nums) { if (nums.size() == 0) return -1; sort(nums.begin(), nums.end()); return nums[nums.size()/2];}

上一篇：Wechat--小开发

下一篇：Unix网络编程—— shutdown与close