对于一个必定存在一个出现次数至少为

 的众数的数列，最简单的方式为排序法。因为众数超过半数又必定存在，故在中间位置的那个数一定是众数。

#include <iostream>

#include <vector>

#include <algorithm>
using namespace std;


int main()
{
    int n;
    while (cin >> n)
    {
        vector<int> num(n);
        for (int i = 0; i < n; i++)
        {
            cin >> num[i];
        }

        int mid = (n + 1) / 2;
        sort(num.begin(), num.end());

        cout << num[mid] << endl;

    }

    return 0;
}

排序法的时间复杂度为O(n log n)，空间复杂度为O(log n) ~ O(n)。排序法的弊端是，只能找 

摩尔投票法的核心思想为一换一抵消。

 时，假设数列总共有N个数，众数出现的次数 > N/2 ，大于其他数的总和。因此在一换一抵消的过程中，留下的一定是众数。

#include <iostream>

#include <vector>

#include <algorithm>
using namespace std;


int majorityElement(vector<int> &nums)
{
    // 当前候选元素

    int candidate;


    // 计数
    int count = 0;
    for (int i : nums)
    {
        // 当前票数为0说明抵消，重新选择候选
        if (count == 0)
        {
            candidate = i;
            count = 1;

        }
        // 如果相同则投票 + 1
        else if (i == candidate)
        {
            count++;
        }
        // 不同则 - 1
        else
        {
            count--;
        }
    }
    return candidate;

}


int main()
{
    int n;
    while (cin >> n)
    {
        vector<int> num(n);
        for (int i = 0; i < n; i++)
        {
            cin >> num[i];

        }

        cout << majorityElement(num) << endl;
    }

    return 0;
}

时间复杂度为O(n),空间复杂度为O(1)

时，抵消的思想从一对一变成多对一。

 个。因为当且仅当个数x = n / k 时 才能有k个。故

因此我们维护一个候选人组，遍历数组时，若候选人组未满 k - 1个，则加入候选人组，若已满则所有候选人组都 - 1。

为什么候选人未满时要加入而不是抵消？

考虑这样一种情况： 数组: [1, 1, 1, 2, 2, 2, 3] (n=7, 找>n/3即>2.33次的元素)

 正确结果：1出现3次，2出现3次，都应该被找到 

4(遇到2): 1减1 → {1:2}  (2不加入)

5(遇到2): 1减1 → {1:1}  (2不加入)  

6(遇到2): 1减1 → {1:0}删除 → {} (2不加入)

最终结果：只有3！  完全错了！

那为什么要加入呢？ 因为实际上真正的众数的个数一定比非众数的个数多，所以无论我们加入的是众数还是非众数，在后续的抵消过程中，票数少的一定会被票数多的所抵消。但此时我们还不能确定这个数是否是众数。所以当我们得到最后的候选人组时，还需要最后的验证。

unordered_map<int, int> candidate;
    for (int i = 0; i < nums.size(); i++)
    {
        //如果已经是候选，则票数++
        if (candidate.count(nums[i]))
        {
            candidate[nums[i]]++;
        }
        //如果非候选，且候选人未满则加入候选
        else if (candidate.size() < k - 1)
        {
            candidate[nums[i]] = 1;
        }
        //否则所有人票数-1
        else
        {
            vector<int> toRemove;
            //注意 it是拷贝，所以我们需要引用来修改值
            for (auto &it : candidate)
            {
                it.second--;

                if (it.second == 0)
                {
                    toRemove.push_back(it.first);
                }
            }

            for (auto it : toRemove)
            {
                candidate.erase(it);
            }
        }
    }

我们需要回到原数组对我们得到的候选人数组进行验证，验证每一个候选人的出现次数，才能得到最终的众数数组。

vector<int> majorityElement(vector<int> nums, int k)

{
    unordered_map<int, int> candidate;
    for (int i = 0; i < nums.size(); i++)
    {
        if (candidate.count(nums[i]))
        {
            candidate[nums[i]]++;
        }

        else if (candidate.size() < k - 1)
        {
            candidate[nums[i]] = 1;
        }

        else
        {
            vector<int> toRemove;

            for (auto &it : candidate)
            {
                it.second--;

                if (it.second == 0)
                {
                    toRemove.push_back(it.first);
                }
            }
            for (auto it : toRemove)
            {
                candidate.erase(it);
            }

        }
    }
    vector<int> res;
    for (auto can : candidate)
    {
        int count = 0;

        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] == can.first)
            {
                count++;
            }
        }
        if (count > (nums.size() / k))
            res.push_back(can.first);
    }

    return res;
}

#include <iostream>

#include <vector>

#include <algorithm>
#include <unordered_map>
using namespace std;

vector<int> majorityElement(vector<int> nums, int k)
{
    unordered_map<int, int> candidate;
    for (int i = 0; i < nums.size(); i++)
    {

        if (candidate.count(nums[i]))
        {
            candidate[nums[i]]++;
        }
        else if (candidate.size() < k - 1)
        {
            candidate[nums[i]] = 1;
        }
        else
        {
            vector<int> toRemove;

            for (auto &it : candidate)
            {
                it.second--;
                if (it.second == 0)
                {
                    toRemove.push_back(it.first);
                }
            }
            for (auto it : toRemove)
            {

                candidate.erase(it);
            }
        }

    }
    vector<int> res;
    for (auto can : candidate)

    {
        int count = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] == can.first)
            {
                count++;
            }
        }
        if (count > (nums.size() / k))
            res.push_back(can.first);
    }

    return res;
}

int main()
{
    int n;
    while (cin >> n)
    {
        vector<int> num(n);
        for (int i = 0; i < n; i++)
        {
            cin >> num[i];
        }
        vector<int> res = majorityElement(num, 2);
        for (int i = 0; i < res.size(); i++)
        {
            cout << res[i] << " ";
        }
        cout << endl;
    }

    return 0;
}

状态转移方程：把图形转换为二维数组可知，只能由左上方和正上方能到达当前位置。故有

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + f[i][j];

#include <iostream>

#include <vector>

#include <algorithm>
using namespace std;


int main()
{
    int n;
    cin >> n;
    for (int k = 0; k < n; k++)
    {
        int r;
        cin >> r;
        vector<vector<int>> f(r, vector<int>(r, 0));

        for (int i = 0; i < r; i++)
        {

            for (int j = 0; j <= i; j++)
            {
                cin >> f[i][j];
            }
        }
        // dp[i][j] 表示走到(i,j)位置的数字和
        vector<vector<int>> dp(r, vector<int>(r, 0));

        dp[0][0] = f[0][0];
        int maxSum = dp[0][0];
        for (int i = 1; i < r; i++)

        {

            for (int j = 0; j <= i; j++)
            {
                if (j - 1 >= 0)
                {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + f[i][j];
                }
                else
                {
                    dp[i][j] = dp[i - 1][j] + f[i][j];
                }
                if (dp[i][j] > maxSum)
                {
                    maxSum = dp[i][j];
                }
            }
        }


        cout << maxSum << endl;
    }

    return 0;
}

本题是一个完全背包问题，每一个硬币可以使用无数次。

dp[i]表示容量为i的背包的最小价值。

// 状态转移方程
        for (int i = 1; i <= weight; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i - coins[j].second >= 0 && dp[i - coins[j].second] != INT_MAX)
                {
                    dp[i] = min(dp[i], dp[i - coins[j].second] + coins[j].first);
                }
            }
        }

每种硬币前的状态 + 当前硬币的价值

的最小值。注意判断不可行方案，若前置状态不可行则跳过。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int t;
    cin >> t;
    for (int k = 0; k < t; k++)
    {
        // 空与满的重量
        int e, f;
        cin >> e >> f;

        // 硬币种类
        int n;
        cin >> n;

        // 硬币的价值与重量
        vector<pair<int, int>> coins(n);
        for (int i = 0; i < n; i++)
        {
            cin >> coins[i].first >> coins[i].second;
        }

        // 硬币重量
        int weight = f - e;

        // dp[i]表示容量为i的背包的最小价值
        vector<int> dp(weight + 1, INT_MAX);

        // 边界条件
        for (int i = 0; i <= n; i++)
        {
            dp[0] = 0;
        }

        // 状态转移方程
        for (int i = 1; i <= weight; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i - coins[j].second >= 0 && dp[i - coins[j].second] != INT_MAX)
                {
                    dp[i] = min(dp[i], dp[i - coins[j].second] + coins[j].first);
                }
            }
        }

        if (dp[weight] == INT_MAX)
        {
            cout << "This is impossible." << endl;
        }
        else
        {
            cout << "The minimum amount of money in the piggy-bank is " << dp[weight] << "." << endl;
        }
    }

    return 0;
}

对于一个必定存在一个出现次数至少为(n + 1)/ 2 的众数的数列，最简单的方式为排序法。因为众数超过半数又必定存在，故在中间位置的那个数一定是众数。

Coding day 9

算法

编程语言

后端

学习众数查找算法与动态规划实战：排序法、摩尔投票法解决HDU1029众数问题，数塔DP解决HDU2084，完全背包处理HDU1114。掌握O(n)时间复杂度的摩尔投票法核心思想，理解动态规划状态转移方程的应用场景与实现技巧，提升算法解题能力。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

Coding day 9

Coding day 9

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐