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.
这道题有很多种解法，可以排序之后，直接返回中间值，时间复杂度为O(nlogn)，可以hash之后找到数量最大的那个值，时间复杂度为O(n)，但是需要额外的空间。我用的是计数法，具体看代码，时间复杂度为O(n)，也不需要额外的空间。
1 class Solution { 2 public: 3 int majorityElement(vector<int> &num) { 4 int Number;int count=0; 5 if(num.empty()) 6 return 0; 7 for(auto v:num){ 8 if(count == 0) 9 Number = v; 10 if(Number == v) 11 count++; 12 else 13 count--; 14 } 15 return Number; 16 } 17 };
转载于:https://www.cnblogs.com/desp/p/4340363.html
相关资源：JAVA上百实例源码以及开源项目