1.题目描述

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的元素。假设一定存在

2.分析

统计了一下几种解法： （1）找数组中位数。参考快排的partition函数，pivot=mid，就是中位数。或者暴力一点，直接排序后取中位数。 （2）多数投票算法Majority Vote Algorithm。 一次遍历，O(n)。大概思想是：元素相同->count++(赞同票),元素不同->count–(反对票)。大多数元素的个数>n/2。所以最后胜出的必然是大多数。 （3）对元素出现次数计数，选出出现次数>n/2。 （4）随机数。随机挑选一个元素，对这个元素计数判断是否>n/2次。有大于50%的概率会选中，所以还是比较巧妙的方法。

3.代码

c++ 快排的partition

int partition(vector<int>& nums, int left,int right) { int pivot = nums[left]; int low = left; int high = right; while (low < high) { while (low<high && nums[high]>=pivot) --high; nums[low] = nums[high]; while (low < high && nums[low] <= pivot) ++low; nums[high] = nums[low]; } nums[low] = pivot; return low; } int majorityElement(vector<int>& nums) { int low = 0; int high = nums.size() - 1; int mid = (low + high) / 2; int pivot = partition(nums, low, high); while (pivot != mid) { if (pivot < mid) pivot = partition(nums, pivot + 1, high); else pivot = partition(nums, low, pivot - 1); } return nums[pivot]; }

Majority Vote Algorithm

int majorityElement(vector<int>& nums) { int count = 0; int candidate; for (int n : nums) { if (count == 0) { ++count; candidate = n; } else { if (n == candidate) ++count; else --count; } } return candidate; }

随机数

int majorityElement(vector<int>& nums) { int n = nums.size(); srand(unsigned(time(NULL))); while (true) { int index = rand() % n; int count = 0; for (int n : nums) if (n == nums[index]) ++count; if (count > n / 2) return nums[index]; } }