169.Majority Element
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.
这道题要求寻找数组中的多数元素，也就是出现次数超过数组长度一半的元素，最容易想到的方式就是用两个指针对其进行扫描，再用一个count变量进行计数，遇到count超过数组长度一半的情况就返回，思路非常简单，代码如下:
class Solution {
public:
int majorityElement(vector<int>& nums) {
if(nums.size()<2)
return nums[0];
int i=0,j=0,size=nums.size(),count=0;
int half=size/2;;
for(i=0;i<size;i++){
count=0;/*外循环每进行一次count计数变量应该重新置0*/
for(j=0;j<size;j++){
if(nums[j]==nums[i]){
count++;
if(count>half)
return nums[i];
}
}
}
return -1;
}
};
这并不能称得上是一个高效的算法，因为就是在反复的遍历，不出所料这个算法提交之后超时了，对于小数组来说没什么问题，但对于有大量重复元素的数组而言这样去遍历就显得太多余了，于是我用了之前做题时学到的一个技巧对算法进行了优化，代码如下:
/*solution1 O(n^2) 20ms*/
class Solution {
public:
int majorityElement(vector<int>& nums) {
if(nums.size()<2)
return nums[0];
int i=0,j=0,size=nums.size(),count=0;
int half=size/2;;
for(i=0;i<size;i++){
count=0;/*外循环每进行一次count计数变量应该重新置0*/
/*遇到有重复元素的，我们仅以最后一个元素做参照，来对该元素出现次数进行统计*/
while(nums[i]==nums[i+1])
i++;
for(j=0;j<size;j++){
if(nums[j]==nums[i]){
count++;
if(count>half)
return nums[i];
}
}
}
return -1;
}
};
这样一个简单的操作，让一个TLE的算法击败了百分之五十以上的提交，运行时间为20ms。
之后又思考了别的方法，主要是以下三种:
1.sort
既然是majority，在经过排序后，如果比较小，从第一个元素开始，那么最后一个majority必然位于中间位置;如果比较大，导致最后一个元素也为majority，那么中间位置也依然是majority;综上所述，在两种极端情况下，都可以保证中间是majority，那么在其他情况下一定可以保证最中间的元素是majority。
既然如此，代码也就十分容易写出了；
/*solution2 sort 40ms*/
class Solution {
public:
int majorityElement(vector<int>& nums) {
sort(nums.begin(),nums.end());
return nums[nums.size()/2];
}
};
时间复杂度为O(nlog n），速度并不是很快，那么有没有办法将时间复杂度降到O(n)呢？
2.hash-table
hash-table的思路比较直接，维护一个unodered-map ,每次在hash-table里搜索nums[i]，搜索到则让以nums[i]为键值的元素加1即可，见代码:
/*solution4 use hash-table time-complexity O(n) memory-complexity O(n)*/
class Solution {
public:
int majorityElement(vector<int>& nums) {
if(nums.size()<2)
return nums[0];
unordered_map<int,int> num_count;
int i=0,size=nums.size();
for(i=0;i<size;i++){
if(num_count.find(nums[i])==num_count.end())
num_count[nums[i]]=0;
else
num_count[nums[i]]++;
if(num_count[nums[i]]>=size/2)
return nums[i];
}
return -1;
}
};
时间复杂度O(n),空间复杂度O(n)，但leetcode给出的运行时间为48ms，看来还需要再优化
3.majority voting algorithm
这个算法专门用来解决数组中多数元素的问题，只需要one-pass就可以解决问题
先来看看这个算法的描述:
The algorithm is carried out in two steps:
Eliminate all elements except one. Iterating through the array of numbers, maintain a current candidate and a counter initialized to 0. With the current element x in iteration, update the counter and (possibly) the candidate: if the counter is 0, set the current candidate to x and the counter to 1. If the counter is not 0, increment or decrement the counter based on whether x is the current candidate. Determine if the remaining element is a valid majority element. With the candidate acquired in step 1, iterate through the array of numbers and count its occurrences. Determine if the result is more than half of the sequence’s length. If so, the candidate is the majority. Otherwise, the sequence doesn’t contain a majority.
主要思想是:
- 不断删除数组中的元素直到仅剩下一个
- 判断剩下的那一个是否真的是majority
关于这个算法的演示，请见：http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html#step13
下面贴出代码:
class Solution {
public:
int majorityElement(vector<int>& nums) {
int curIndex=0,count=0,i=0;
for(i=0;i<nums.size();i++){
nums[curIndex]==nums[i]?count++:count--;
if(!count){
curIndex=i;
count=1;
}
}
return nums[curIndex];
}
};