数组分成两组差值最小java,差分数组的定义及用途

　　00-1010序应用场景Leetcode话题实战话题描述思维代码

　　00-1010昨天(2022-06-07)第一次看到这个超级简单但是很实用的算法——差数组。差数组由原数组演化而来，其值为原数组的当前位置值减去前一个位置的值。从下图可以清楚的看到。

　　从上图我们可以清楚的看到，diff array[1]=-3=srcarray[1]-srcarray[0]=-1-2。所以当我们知道差数组的时候，如何推导原数组也是基于上面的关系，但是我们需要从index=0开始用原数组的前一个值累加当前差数组。

　　00-1010想象一个场景。我们需要给0 ~ 8位的值加上相同的值。如果对原数组进行运算，需要改变9个位置的值，但对差分数组进行运算时，只需要改变两个位置的值，即位置0和8分别加值。我们可以通过差分阵列得到位置0 ~ 8之间其他位置的正确值。

　　这样，在一次更新大量数据的情况下，性能提升更加明显。

目录

　　00-1010当k个排班有一些时间交叉时(比如所有k个排班都在同一时间)，就会产生k个预订。给你一些排班【开始，结束】，每增加一个排班请返回一个整数K，表示之前所有排班会产生的最大K个预订量。实现一个MyCalendarThree类来存储您的日程表。您可以随时添加新的计划。MyCalendarThree()初始化对象。Int book(int start，int end)返回一个整数k，它表示日历中存在的k个预订的最大值。提示：0=startend=10 9每个测试用例，book函数最多被调用不超过400次。

　　00-1010在上面的题目描述中，如果时间点重合，并且这个时间点预定为1次，最容易想到的就是暴力解决。每出现一个时间点，时间点预定为1次，但是看数据量，最大值是10 ^ 9。如果只有一个时间段[0-10 ^ 9]，那么我们在时间和空间上都失去了很多。这时候我们可以用上面说的差数组，只需要更新开始时间和结束时间，然后计算。我们可以用一个映射来存储差分数组变化的最终结果(差分数组的起始值都是0)，关键是起始时间或者结束时间点，值是预定的次数。当一个schedule [start，end]出现时，我们需要设置预定次数1的起始位置，但是因为是开区间，所以end不包含在这个schedule中，相当于原数组中end-1位置的值1，但是end位置的值不变，所以在差分数组中。我们来看看具体的实现代码。

前言

TreeMapInteger，IntegertreeMappublicMyCalendarThree(){ treeMap=new treeMap()；}publicintbook(intstart，intent){ if(！treemap . contains key(start)){ treemap . put(start，0)；}如果(！treemap . contains key(end)){ treemap . put(end，0)；} treeMap.put(start，treemap . get(start)1)；treeMap.put(end，treemap . get(end)-1)；//x1-0=value 1 x2-x1=value 2 int answer=0；int max=0；for(integer value : treemap . values()){ max=value；answer=Math.max(max，答案)；} returnanswer}就是这样。本文对Java实现差分数组的详细说明就介绍到这里。有关Java差分数组的更多信息，请搜索popular IT以前的文章或继续浏览下面的相关文章。我希望你以后能更多地支持流行音乐！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。