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

发布时间:2024年01月15日

关键词:排序?摩尔投票法

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

题目:库存管理 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一样,就+1
            else votes+=-1;//不一样就-1
        }
        return x;
    }
};
文章来源:https://blog.csdn.net/rainssssss/article/details/135611743
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。