【贪心算法】【中位贪心】LeetCode:100123.执行操作使频率分数最大

这篇具有很好参考价值的文章主要介绍了【贪心算法】【中位贪心】LeetCode:100123.执行操作使频率分数最大。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

涉及知识点

双指针
C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
贪心算法

题目

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
你可以对数组执行 至多 k 次操作:
从数组中选择一个下标 i ,将 nums[i] 增加 或者 减少 1 。
最终数组的频率分数定义为数组中众数的 频率 。
请你返回你可以得到的 最大 频率分数。
众数指的是数组中出现次数最多的数。一个元素的频率指的是数组中这个元素的出现次数。
示例 1:
输入:nums = [1,2,6,4], k = 3
输出:3
解释:我们可以对数组执行以下操作:

  • 选择 i = 0 ,将 nums[0] 增加 1 。得到数组 [2,2,6,4] 。
  • 选择 i = 3 ,将 nums[3] 减少 1 ,得到数组 [2,2,6,3] 。
  • 选择 i = 3 ,将 nums[3] 减少 1 ,得到数组 [2,2,6,2] 。
    元素 2 是最终数组中的众数,出现了 3 次,所以频率分数为 3 。
    3 是所有可行方案里的最大频率分数。
    示例 2:
    输入:nums = [1,4,4,2,4], k = 0
    输出:3
    解释:我们无法执行任何操作,所以得到的频率分数是原数组中众数的频率 3 。
    参数范围
    1 <= nums.length <= 105
    1 <= nums[i] <= 109
    0 <= k <= 1014

贪心算法(中位数贪心)

假定众数是x,假定nums的长度为n,将nums按升序排序。

x一定是nums中的数

我们用反证发证明。

x < nums[0] 所有数先降到nums[0],再由nums[0]降到x,不如直接降到nums[0]
x > nums[n-1] 所有数先升到nums[n-1],再升到x,不如只升到nums[n-1]
x在nums[i]和nums[j]之间,nums中比x小的a个数,比x大的b个数。 如果a>=b,x–,可以节省a-b个操作,直到x等于nums[i];否则x++,直到x等于nums[j]。

改变的数一定是一个子数组

假定改变的数是两个子数组[i1,i2]和[i3,i4]。如果x在[i1,i2]之间,则将i4替换成i2+1,直到两个子数组挨着一起合并。如果x在[i3,i4]之间,则i1替换i3-1,直到两个子数组挨着一起合并。

x只需要考虑中位数(中位数贪心算法)

来证明贪心算法的正确性。假定x是nums[i],x前面的数a个,x后面的数b个,i变成i-1操作次数变化:b-(a-1),如果表达式大于等于0,则没必要左移。b -a+1 >= 0,即a <=b+1。同理b <=a+1。即abs(a-b)<=1,则没必要左移和右移。
即:
如果n为偶数,中间任意一个。
如果n为奇数,中间的那个。

代码

核心代码

class Solution {
public:
	int maxFrequencyScore(vector<int>& nums, long long k) {
		m_c = nums.size();
		sort(nums.begin(), nums.end());
		vector<long long> vPreSum = { 0 };
		for (const auto& n : nums)
		{
			vPreSum.emplace_back(n+vPreSum.back());
		}	
		int iRet = 0;
		for (int left = 0, right = 0; left < m_c; left++)
		{
			while (right <= m_c)
			{
				const long long mid = left + (right - left) / 2;
				const long long llLessNeed = (mid - left) * nums[mid] - (vPreSum[mid] - vPreSum[left]);
				const long long llEqualMoreNeed = (vPreSum[right] - vPreSum[mid]) - nums[mid] * (right - mid);
				if (llLessNeed + llEqualMoreNeed <= k)
				{
					iRet = max(iRet, right - left);
					right++;
				}
				else
				{
					break;
				}
			}			
		}
		return iRet;
	}
	int m_c;
};

测试用例

void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}
}

int main()
{
	Solution slu;
	vector<int> nums;
	int k;
	{
		Solution slu;
		nums = { 1,4,4,2,4 }, k = 0;
		auto res = slu.maxFrequencyScore(nums, k);
		Assert(3, res);
	}
	{
		Solution slu;
		nums = { 16, 2, 6, 20, 2, 18, 16, 8, 15, 19, 22, 29, 24, 2, 26, 19 }, k = 40;
		auto res = slu.maxFrequencyScore(nums, k);
		Assert(11, res);
	}
	
	{
		Solution slu;
		nums = { 1, 2, 6, 4 }, k = 3;
		auto res = slu.maxFrequencyScore(nums, k);
		Assert(3, res);
	}

	
	//CConsole::Out(res);
}

错误解法:二分查找+双指针

错误原因: 随着left增加targge可能减少
class Solution {
public:
int maxFrequencyScore(vector& nums, long long k) {
m_c = nums.size();
sort(nums.begin(), nums.end());
vector vPreSum = { 0 };
for (const auto& n : nums)
{
vPreSum.emplace_back(n+vPreSum.back());
}
long long llLeftSum = 0;//nums[left,target)的和,nums升序
int iRet = 0;
for (int left = 0, target = 0; left < m_c; left++)
{
while ((target < m_c) && (nums[target]*(target-left)- llLeftSum <= k))
{
const int right = BF(vPreSum,nums, target, k - (nums[target] * (target - left) - llLeftSum));
iRet = max(iRet, right - left);
llLeftSum += nums[target];
target++;
}
llLeftSum -= nums[left];
}
return iRet;
}
int BF(const vector& vPreSum,const vector& nums, int index,long long canUse)
{
int left = index, right = vPreSum.size();
while (right - left > 1)
{
const int mid = left + (right- left)/2 ;
if ((vPreSum[mid] - vPreSum[index]- nums[index] * (mid - index)) <= canUse)
{
left = mid;
}
else
{
right = mid;
}
}
return left;
}
int m_c;
};

【贪心算法】【中位贪心】LeetCode:100123.执行操作使频率分数最大,# 算法题,leetcode,算法,贪心算法,c++,前缀和,中位贪心,频率

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

【贪心算法】【中位贪心】LeetCode:100123.执行操作使频率分数最大,# 算法题,leetcode,算法,贪心算法,c++,前缀和,中位贪心,频率文章来源地址https://www.toymoban.com/news/detail-763707.html

到了这里,关于【贪心算法】【中位贪心】LeetCode:100123.执行操作使频率分数最大的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2530. 执行 K 次操作后的最大分数

    2530. 执行 K 次操作后的最大分数 难度: 中等 来源: 每日一题 2023.10.18 给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的 起始分数 为 0 。 在一步 操作 中: 选出一个满足 0 = i nums.length 的下标 i , 将你的 分数 增加 nums[i] ,并且 将 nums[i] 替换为 ceil(nums[i] / 3) 。 返回在

    2024年02月07日
    浏览(40)
  • C++深度优先搜索的应用:在树上执行操作以后得到的最大分数

    深度优先搜索(DFS) 有一棵 n 个节点的无向树,节点编号为 0 到 n - 1 ,根节点编号为 0 。给你一个长度为 n - 1 的二维整数数组 edges 表示这棵树,其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 有一条边。 同时给你一个长度为 n 下标从 0 开始的整数数组 values ,其中 values[i] 表示第

    2024年02月05日
    浏览(43)
  • 算法沉淀——贪心算法一(leetcode真题剖析)

    贪心算法(Greedy Algorithm)是一种基于贪心策略的优化算法,它通常用于求解最优化问题,每一步都选择当前状态下的最优解,以期望通过局部最优的选择最终达到全局最优。贪心算法的思想是在每一步都做出在当前状态下局部最优的选择,而不考虑未来可能造成的影响。 在

    2024年03月08日
    浏览(48)
  • 算法沉淀——贪心算法六(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/broken-calculator/ 在显示着数字 startValue 的坏计算器上,我们可以执行以下两种操作: **双倍(Double):**将显示屏上的数字乘 2; **递减(Decrement):**将显示屏上的数字减 1 。 给定两个整数 startValue 和 target 。返回显示数字 target 所需的最小操

    2024年04月11日
    浏览(43)
  • 算法沉淀——贪心算法七(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/integer-replacement/ 给定一个正整数 n ,你可以做如下操作: 如果 n 是偶数,则用 n / 2 替换 n 。 如果 n 是奇数,则可以用 n + 1 或 n - 1 替换 n 。 返回 n 变为 1 所需的 最小替换次数 。 示例 1: 示例 2: 示例 3: 提示: 1 = n = 2^31 - 1 思路 这里我们

    2024年03月23日
    浏览(46)
  • 算法沉淀——贪心算法二(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/longest-increasing-subsequence/ 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如, [3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1: 示

    2024年03月19日
    浏览(49)
  • 算法沉淀——贪心算法五(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/jump-game-ii/ 给定一个长度为 n 的 0 索引 整数数组 nums 。初始位置为 nums[0] 。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处: 0 = j = nums[i] i + j n 返回到达 nums[n - 1] 的最小跳跃次

    2024年04月11日
    浏览(48)
  • 算法沉淀——贪心算法三(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/ 给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。 在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。 返回 你能获得

    2024年03月24日
    浏览(38)
  • leetcode系列贪心算法汇总

    11 盛水最多的容器 题目:给一个一维数组,大概的意思就是下标代表水槽的宽度,数组的值代表这个位置水槽的高度,求盛水最多的容量。 解析:肯定得有个临时变量来存最大值,且不断进行比较来更新最大值,然后分别从两边开始使用双指针进行遍历,tmp := (right - left)

    2024年02月07日
    浏览(44)
  • 【leetcode】贪心算法介绍

    详细且全面地分析贪心算法常用的解题套路、数据结构和代码逻辑如下: 找最值型: 每一步选择都是局部最优解,最后得到的结果就是全局最优解。 常用于找零钱问题、区间覆盖问题等。 一般情况下,可以通过排序将数据进行处理,然后逐步选择最优解。 区间问题: 将问

    2024年02月21日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包