涉及知識點

雙指針
C++算法：前綴和、前綴乘積、前綴異或的原理、源碼及測試用例 包括課程視頻
貪心算法

題目

給你一個下標(biāo)從 0 開始的整數(shù)數(shù)組 nums 和一個整數(shù) k 。
你可以對數(shù)組執(zhí)行 至多 k 次操作：
從數(shù)組中選擇一個下標(biāo) i ，將 nums[i] 增加 或者 減少 1 。
最終數(shù)組的頻率分?jǐn)?shù)定義為數(shù)組中眾數(shù)的 頻率 。
請你返回你可以得到的 最大 頻率分?jǐn)?shù)。
眾數(shù)指的是數(shù)組中出現(xiàn)次數(shù)最多的數(shù)。一個元素的頻率指的是數(shù)組中這個元素的出現(xiàn)次數(shù)。
示例 1：
輸入：nums = [1,2,6,4], k = 3
輸出：3
解釋：我們可以對數(shù)組執(zhí)行以下操作：

• 選擇 i = 0 ，將 nums[0] 增加 1 。得到數(shù)組 [2,2,6,4] 。
• 選擇 i = 3 ，將 nums[3] 減少 1 ，得到數(shù)組 [2,2,6,3] 。
• 選擇 i = 3 ，將 nums[3] 減少 1 ，得到數(shù)組 [2,2,6,2] 。
  元素 2 是最終數(shù)組中的眾數(shù)，出現(xiàn)了 3 次，所以頻率分?jǐn)?shù)為 3 。
  3 是所有可行方案里的最大頻率分?jǐn)?shù)。
  示例 2：
  輸入：nums = [1,4,4,2,4], k = 0
  輸出：3
  解釋：我們無法執(zhí)行任何操作，所以得到的頻率分?jǐn)?shù)是原數(shù)組中眾數(shù)的頻率 3 。
  參數(shù)范圍：
  1 <= nums.length <= 10⁵
  1 <= nums[i] <= 10⁹
  0 <= k <= 10¹⁴

貪心算法（中位數(shù)貪心)

假定眾數(shù)是x,假定nums的長度為n，將nums按升序排序。

x一定是nums中的數(shù)

我們用反證發(fā)證明。

改變的數(shù)一定是一個子數(shù)組

假定改變的數(shù)是兩個子數(shù)組[i1,i2]和[i3,i4]。如果x在[i1,i2]之間，則將i4替換成i2+1，直到兩個子數(shù)組挨著一起合并。如果x在[i3,i4]之間，則i1替換i3-1，直到兩個子數(shù)組挨著一起合并。

x只需要考慮中位數(shù)（中位數(shù)貪心算法)

來證明貪心算法的正確性。假定x是nums[i]，x前面的數(shù)a個，x后面的數(shù)b個，i變成i-1操作次數(shù)變化：b-(a-1)，如果表達(dá)式大于等于0，則沒必要左移。b -a+1 >= 0，即a <=b+1。同理b <=a+1。即abs(a-b)<=1，則沒必要左移和右移。
即：
如果n為偶數(shù)，中間任意一個。
如果n為奇數(shù)，中間的那個。

代碼

核心代碼

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;
};

擴展閱讀

視頻課程

有效學(xué)習(xí)：明確的目標(biāo) 及時的反饋 拉伸區(qū)（難度合適），可以先學(xué)簡單的課程，請移步CSDN學(xué)院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成戰(zhàn)斗了，為老板分憂，請學(xué)習(xí)C#入職培訓(xùn)、C++入職培訓(xùn)等課程
https://edu.csdn.net/lecturer/6176

相關(guān)下載

想高屋建瓴的學(xué)習(xí)算法，請下載《喜缺全書算法冊》doc版
https://download.csdn.net/download/he_zhidan/88348653

測試環(huán)境

操作系統(tǒng)：win7 開發(fā)環(huán)境： VS2019 C++17
或者 操作系統(tǒng)：win10 開發(fā)環(huán)境： VS2022 C++17
如無特殊說明，本算法用**C++**實現(xiàn)。

文章來源地址http://www.zghlxwxcb.cn/news/detail-763707.html

到了這里，關(guān)于【貪心算法】【中位貪心】LeetCode:100123.執(zhí)行操作使頻率分?jǐn)?shù)最大的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！