我必须为我的任务找到最好的算法(复杂性) .
输入:索引first,last和array
输出:在第一个和最后一个位置之间进行排序后,同一数组中的整数之和 .
数组中的数字是不同的(可以是负数)!
例如:输入:first = 3,last = 7,array = {5,4,2,6,8,9,0,-1,3}
产量:26(3 4 5 6 8)
我尝试了什么=>
-
我们可以轻松排序数组并计算它,它将是O(nlogn)
-
我们可以计算数组中元素数量与我们的索引的第一个和最后一个之间的差异,并选择最大元素的计数数量或最小值,并从我们的实际数组总和中删除 .
例如:计算(n-last)最大整数的总和,然后计算(first-0)最小整数的总和并从我们的实际总和中减去,但是它并不总是好主意,因为找到这个最大或最小整数的数量在数组中可能很昂贵 . 当然,我可以很容易地进行一些改进,例如计算何时最好采用(n-last)最大数字或仅(最后)最大数字的总和 .
我要问的是,是否有更好的解决方案来解决这个问题,然后解决一些方程式并制作大量的if来改进它 .
2 回答
看一下
std::nth_element
算法,该算法将"first N"与"elements past N"分开,而无需在两个分区内进行额外的排序工作 .为了您的目的,您需要两次调用
nth_element
. 第二个调用将在第一步中创建的一个分区上,而不是整个数组 . 最后,您将有三个分区:元素少于您需要的元素
您需要的元素
元素大于你需要的元素
它通常在线性时间内完成,尽管最坏情况仍为O(N lg N)
这是一种比OP提出的解决方案更快的方法 . 虽然不像@BenVoigt提供的优秀解决方案那样优雅或一般,但它几乎同样快 .
我们首先创建两个足够大的向量,以跨越整个输入值范围 . 其中一个保持输入向量的值,另一个保持该值的值(上面的频率向量) . 元素按顺序添加,因为索引是从值本身构成的 .
然后我们遍历频率向量并将我们的两个边界之间的结果值相加 . 上述方法的一个缺点是,如果输入向量中存在重复值,它通常会返回不正确的结果 . 感谢@BenVoigt的建议,上面的内容现在可以处理具有重复值的输入向量 . 如您所见,边缘需要注意(因此额外的
if ((count - upper) > 1)
以及if ((count - lower) >= 1 && firstHit)
之后的线) .以下是一些非常基本的基准测试,真正展示了@BenVoigt提供的解决方案的强大功能 . 首先,这是OP的实现和使用
std::nth_element
的实现 .这是用于测试的主要功能,我可能会添加一些粗略的功能:
我的电脑上的结果*(我正在使用
clang++
):正如您所看到的,使用@BenVoigt提供的
std::nth_element
在速度和通用性方面都是优越的,而索引方法仍然比天真的方法快得多 .gcc
)的结果 .