数据结构学习 jz39 数组中出现次数超过一半的数字

关键词：排序 摩尔投票法

摩尔投票法没学过所以没有想到，其他的都自己想。

题目：库存管理 II

方法一：

思路：

排序然后取中间值。因为超过一半所以必定在中间值是我们要的结果。

复杂度计算：

时间复杂度O(nlogn)

空间复杂度O(1)

代码：

class Solution {
public:int inventoryManagement(vector<int>& stock) {if(stock.size()==1) return stock[0];sort(stock.begin(),stock.end());return stock[stock.size()/2];}
};

方法二：

哈希表统计法。

思路：

哈希表统计一遍，如果结果大于一半就返回。

复杂度计算：

时间复杂度O(n)

空间复杂度O(k)数的总类

代码：

class Solution {
public:int inventoryManagement(vector<int>& stock) {if(stock.size()==1) return stock[0];unordered_map<int,int> hash;for(int i=0;i<stock.size();++i){hash[stock[i]]++;if(hash[stock[i]]>stock.size()/2) return stock[i];}return 0;}
};

方法三：最佳解法

 摩尔投票法。

思路：

我是看了k神的题解才会的。建议看。

复杂度计算：

时间复杂度O(n)

空间复杂度O(1)

代码：

class Solution {
public:int inventoryManagement(vector<int>& stock) {int x=0;int votes=0;for(const int&num:stock){if(votes==0) x=num;if(num==x) votes+=1;//和假设的众数x一样，就+1else votes+=-1;//不一样就-1}return x;}
};