问题：

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.

Credits:

Special thanks to  for adding this problem and creating all test cases.

解决：

①我首先想到了将数组排序，然后记录每一个数值出现的次数，满足大于N/2的返回即可。耗时6ms。

public class Solution {

    public int majorityElement(int[] nums) {//出现次数大于n/2         int count = 1;          int n = nums.length;         int majority = 0;         Arrays.sort(nums);         if(nums.length == 1) return nums[0];         for (int i = 1;i < nums.length ;i ++ ) {             if (nums[i] == nums[i - 1]) {                 count ++;                 if(count > n / 2){                     majority = nums[i];                     break;                 }             }else{                 count = 1;             }                }         return majority;     } }

②Moore voting algorithm--每找出两个不同的element，就成对删除即count --，最终剩下的一定就是所求的。时间复杂度：O(n)。耗时3ms。

public class Solution {

    public int majorityElement(int[] nums) {         int count = 0;         int majority = 0;         for (int i = 0;i < nums.length ;i ++ ) {             if(count == 0){                 majority = nums[i];                 count ++;             }else if(nums[i] == majority){                 count ++;             }else{                 count --;             }         }         return majority;     } }

③leetcode中建议了很多解法：

第一种是Brute force solution，时间复杂度为O(n2)，顾名思义，遍历数组，依次判断每个元素是否为多数元素。

第二种是Hash table，时间复杂度为O(n)，空间复杂度也为(n)，对数组中的每个元素计数，大于⌊n/2⌋时即为所求结果。

第三种是Sorting，时间复杂度为O(nlogn)，找到第n/2个元素即可。

第四种是Randomization，平均时间复杂度为O(n)，最坏情况为无穷大。随机选一个元素，判断其是否为多数元素。由于选中多数元素的概率大于1/2，尝试次数的期望<2。

class Solution {public:    int majorityElement(vector
    
     & nums) {        int size = nums.size();        while (true) {            int r = nums[rand() % size];            int count = 0;            for (int i = 0; i < size; i++) {                if (r == nums[i]) {                    count++;                }            }            if (count > size >> 1) {                return r;            }        }    }};
    

第五种是Divide and conquer，时间复杂度为O(nlogn)，将数组分成两半，分别递归查找这两部分的多数元素，若两者相同，则为多数元素，若不同，则其中之一必为多数元素，判断其一即可。

第六种是Moore voting algorithm，时间复杂度为O(n)，每找出两个不同的element，就成对删除即count --，最终剩下的一定就是所求的。