C++二分查找算法的应用:长度递增组的最大数目

简介: C++二分查找算法的应用:长度递增组的最大数目

本文涉及的基础知识点

二分查找算法合集

题目

给你一个下标从 0 开始、长度为 n 的数组 usageLimits 。

你的任务是使用从 0 到 n - 1 的数字创建若干组,并确保每个数字 i 在 所有组 中使用的次数总共不超过 usageLimits[i] 次。此外,还必须满足以下条件:

每个组必须由 不同 的数字组成,也就是说,单个组内不能存在重复的数字。

每个组(除了第一个)的长度必须 严格大于 前一个组。

在满足所有条件的情况下,以整数形式返回可以创建的最大组数。

示例 1:

输入:usageLimits = [1,2,5]

输出:3

解释:在这个示例中,我们可以使用 0 至多一次,使用 1 至多 2 次,使用 2 至多 5 次。

一种既能满足所有条件,又能创建最多组的方式是:

组 1 包含数字 [2] 。

组 2 包含数字 [1,2] 。

组 3 包含数字 [0,1,2] 。

可以证明能够创建的最大组数是 3 。

所以,输出是 3 。

示例 2:

输入:usageLimits = [2,1,2]

输出:2

解释:在这个示例中,我们可以使用 0 至多 2 次,使用 1 至多 1 次,使用 2 至多 2 次。

一种既能满足所有条件,又能创建最多组的方式是:

组 1 包含数字 [0] 。

组 2 包含数字 [1,2] 。

可以证明能够创建的最大组数是 2 。

所以,输出是 2 。

示例 3:

输入:usageLimits = [1,1]

输出:1

解释:在这个示例中,我们可以使用 0 和 1 至多 1 次。

一种既能满足所有条件,又能创建最多组的方式是:

组 1 包含数字 [0] 。

可以证明能够创建的最大组数是 1 。

所以,输出是 1 。

参数范围

1 <= usageLimits.length <= 105

1 <= usageLimits[i] <= 109

分析

知识点

假定最长组数为len,则各组长度一定是1,2…len。假定各组长度不是连续的,缺少x,那么将(x…) 都扔掉一个元素,变成[x,…)。持续这个过程至到各组长度连续为至。

只关心各值的数量,不关心值,比如:1,2,3和2,1,3完全相同。故可对数据进行排序。

二分

如果如果能创建n组,则一定能创建n-1组。随着len增加,一定会由能创建变成不能创建。寻找最后一个能创建的len。显然适合用左闭右开的二分。

判断能否创建len组

预处理

目标数组为{1,2…len},源数组为升序排序后的 usageLimits,长度不足则在前面补0。比如:目标数组{1,2,3},源数组{0,3,3};目标数组{0,1,2,3},{1,1,2,2}。

推理

我们用len数组表示目标数组,len[i]的含义,[0,len[i])都会有此元素。

len[i]==usageLimits[i] 刚好
len[i] > usageLimits[i] 不足,需要补缺
len[i] < usageLimits[i] 多余,可以用于补缺

长度为3

由于组内不能有重复元素,所以超过len个元素是无效的。我们用表格分析,那些情况刚好创建3组,没多余的数字。

1,1,1,1,1,1 可以 1填2和3的空缺
1,1,1,1,2 可以 1填2和3的空缺
1,1,2,2 可以 1填3的空缺
2,2,2 可以 2填3的空缺
1,1,1,3 可以 1填2的空缺
1,2,3 可以 不用填空缺
3,3 不可以 1的空缺无法填

猜测

3可以填4及以上缺,如:1333,{2},{3,4},{2,3,4},{1,2,3,4}

如何补缺

假定i1<i2,i2无法补i1的缺,因为i2已经用于[0,i2)不能用于[0,i1)中的任何组。

i1可以补i2的缺。i1只由于[0,i1)组,所以补[i2,…)的缺,不会造成同一组有重复数据。

一个数不会补缺两次

假定k = len[i2] -en[i1],则i1多余不会超过k,

usageLimits[i1]-len[i1] >k

==>usageLimits[i1] >len[i1]+k

==>usageLimits[i1] >len[i2]

因为usageLimits[i2]>=usageLimits[i1]

所以:usageLimits[i2]>len2

所以:i2有多余,和有缺矛盾。

i1多余不会超过k,所以补完i2的缺就空了。

==>无需考虑一个数补两个缺

代码

核心代码

class Solution {
public:
int maxIncreasingGroups(vector& usageLimits) {
m_c = usageLimits.size();
m_v = usageLimits;
sort(m_v.begin(), m_v.end());
int left = 1, right = m_c + 1;
while (right - left > 1)
{
const int mid = left + (right - left) / 2;
if (Can(mid))
{
left = mid;
}
else
{
right = mid;
}
}
return left;
}
bool Can(int len)
{
int i = m_c - 1;
long long llNeed = 0;
for (; len > 0; len–,i–)
{
llNeed -= (m_v[i] - len);
if (m_v[i] >= len)
{
llNeed = max(0LL, llNeed);
}
}
for(;i >= 0 ; i–)
{
llNeed -= m_v[i];
}
return llNeed <= 0;
}
int m_c;
vector m_v;
};

测试用例

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template
void Assert(const vector& v1, const vector& 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 usageLimits;
int res = 0;
usageLimits = { 2,2,2 };
res = slu.maxIncreasingGroups(usageLimits);
Assert(res, 3);
usageLimits = { 1,2,5 };
res = slu.maxIncreasingGroups(usageLimits);
Assert(res, 3);
usageLimits = { 2,1,2 };
res = slu.maxIncreasingGroups(usageLimits);
Assert(res, 2);
usageLimits = { 1,1 };
res = slu.maxIncreasingGroups(usageLimits);
Assert(res, 1);
//CConsole::Out(res);

}

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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


相关文章
|
7天前
|
存储 监控 算法
员工上网行为监控中的Go语言算法:布隆过滤器的应用
在信息化高速发展的时代,企业上网行为监管至关重要。布隆过滤器作为一种高效、节省空间的概率性数据结构,适用于大规模URL查询与匹配,是实现精准上网行为管理的理想选择。本文探讨了布隆过滤器的原理及其优缺点,并展示了如何使用Go语言实现该算法,以提升企业网络管理效率和安全性。尽管存在误报等局限性,但合理配置下,布隆过滤器为企业提供了经济有效的解决方案。
41 8
员工上网行为监控中的Go语言算法:布隆过滤器的应用
|
1天前
|
存储 算法 安全
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
7天前
|
算法 索引
【算法】——二分查找合集
二分查找基础模版和进阶模版,查找元素位置,搜索插入位置,x的平方根,山脉数组的峰顶索引,寻找峰值,点名
|
6天前
|
算法 安全 C++
用 C++ 算法控制员工上网的软件,关键逻辑是啥?来深度解读下
在企业信息化管理中,控制员工上网的软件成为保障网络秩序与提升办公效率的关键工具。该软件基于C++语言,融合红黑树、令牌桶和滑动窗口等算法,实现网址精准过滤、流量均衡分配及异常连接监测。通过高效的数据结构与算法设计,确保企业网络资源优化配置与安全防护升级,同时尊重员工权益,助力企业数字化发展。
31 4
|
7天前
|
存储 缓存 算法
探索企业文件管理软件:Python中的哈希表算法应用
企业文件管理软件依赖哈希表实现高效的数据管理和安全保障。哈希表通过键值映射,提供平均O(1)时间复杂度的快速访问,适用于海量文件处理。在Python中,字典类型基于哈希表实现,可用于管理文件元数据、缓存机制、版本控制及快速搜索等功能,极大提升工作效率和数据安全性。
40 0
|
2月前
|
机器学习/深度学习 人工智能 算法
探索人工智能中的强化学习:原理、算法与应用
探索人工智能中的强化学习:原理、算法与应用
|
2月前
|
机器学习/深度学习 算法 数据挖掘
C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出
本文探讨了C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出。文章还介绍了C语言在知名机器学习库中的作用,以及与Python等语言结合使用的案例,展望了其未来发展的挑战与机遇。
50 1
|
2月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
63 1
|
2月前
|
机器学习/深度学习 监控 算法
基于反光衣和检测算法的应用探索
本文探讨了利用机器学习和计算机视觉技术进行反光衣检测的方法,涵盖图像预处理、目标检测与分类、特征提取等关键技术。通过YOLOv5等模型的训练与优化,展示了实现高效反光衣识别的完整流程,旨在提升智能检测系统的性能,应用于交通安全、工地监控等领域。
|
2月前
|
存储 算法 网络协议
OSPF的SPF算法介绍:原理、实现与应用
OSPF的SPF算法介绍:原理、实现与应用
90 3