我必须为我的任务找到最好的算法(复杂性).
输入:索引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来改进它.
看看std::nth_element算法,该算法将"前N"与"过去N的元素"分开,而不进行在两个分区内进行排序的额外工作.
出于您的目的,您需要拨打nth_element两次电话.第二个调用将在第一步中创建的其中一个分区上,而不是整个数组.最后,您将有三个分区:
它通常在线性时间内完成,尽管最坏情况仍为O(N lg N)