我必须找到我任务的最佳算法(复杂性(。
输入：首先索引，最后和数组
输出：首先和最后一个位置之间排序后同一数组中的整数之和。
数组中的数字不同(可能为负(！
例如：输入：第一个= 3，last = 7，array = {5,4,2,6,8,9,0，-1,3}
输出：26(3 4 5 6 8(
我尝试过的=>
-
我们可以轻松地对数组进行排序并进行计算，它将是o(nlogn(
-
我们可以计算数组中元素数量之间的差异和我们的索引首先和最后一个，然后选择计数的最大元素数量或最小值，然后从我们的数组的实际总和中删除。
例如：计数(n -last(最大整数的总和，然后计数(第一个-0(最小整数的总和，并从我们的实际总和中减去，但是它并不总是好主意，因为找到此数量的最大值或阵列中的最低整数可能很昂贵。当然，我可以轻松地进行一些改进，例如计算何时更好地拿(n-last(最大数字或仅(最后一个(最大数字。
我要的是，是否有更好的解决方案解决一些方程式并制作大量IF来改进它。
看一下std::nth_element算法，该算法将"第一个n"与"过去n elements"分开而不进行两个分区内进行分类的额外工作。
出于您的目的，您需要两次致电nth_element。第二个调用将是在第一步中创建的一个分区之一，而不是整个数组。最后，您将有三个分区：
- 元素比您需要的要素
- 您需要的元素
- 要大于您需要的要素
，通常在线性时间内执行此操作，尽管最差的案例仍然是O(n lg n(
这是一种比OP提出的解决方案快的方法。虽然不像@Benvoigt提供的出色解决方案那样优雅或一般，但它几乎一样快。
double boundedSumJoe(std::vector<int> x, int lower, int upper) {
int myMax = *std::max_element(x.begin(), x.end());
int offSet = std::abs(*std::min_element(x.begin(), x.end())) + 1;
unsigned long int myRange;
if (myMax > 0)
myRange = myMax + offSet; // E.g. if myMax = 10 & myMin = -2, then myRange = 12
else
myRange = offSet;
offSet--;
std::vector<int> frequency(myRange, 0);
std::vector<int> values(myRange, 0);
std::vector<int>::iterator it, itEnd = x.end();
int myIndex;
double mySum = 0;
for (it = x.begin(); it < itEnd; it++) {
myIndex = *it + offSet;
frequency[myIndex]++;
values[myIndex] = *it;
}
int count = 0;
bool firstHit = true;
for (std::size_t j = 0; j < myRange; j++) {
if (frequency[j]) {
if (count >= lower) {
if (count <= upper) {
firstHit = false;
mySum += values[j] * frequency[j];
} else {
if ((count - upper) > 1) {
int k = j - 1;
while (!frequency[k]) {k--;}
mySum -= (values[k] * (count - upper - 1));
}
break;
}
}
count += frequency[j];
if ((count - lower) >= 1 && firstHit) {
firstHit = false;
mySum += (values[j] * (count - lower));
}
}
}
return mySum;
}
我们首先创建两个向量，足以跨越整个输入值范围。其中一个将值保留在输入向量中，另一个将值保持为该值(上面的频率向量(。添加元素按顺序添加，因为索引是由值本身制成的。
然后，我们在频率向量上循环，并在两个界限之间总结产生的值。上述方法的缺点是，如果输入向量中有重复值，则通常会返回不正确的结果。得益于@benvoigt的建议，以上可以处理具有重复值的输入向量。如您所见，边缘需要一些护理(因此，额外的if ((count - upper) > 1)以及if ((count - lower) >= 1 && firstHit)之后的行(。
这是一些非常基本的基准测试，这些基准确实显示了@Benvoigt提供的解决方案的功能。首先，以下是使用std::nth_element的OP的实现和实现。
double boundedSumOP(std::vector<int> x, int lower, int upper) {
double mySum = 0;
std::sort(x.begin(), x.end());
std::vector<int>::iterator it, itEnd = x.begin() + upper;
for (it = x.begin() + lower; it <= itEnd; it++)
mySum += *it;
return mySum;
}
double boundedSumBen(std::vector<int> x, int lower, int upper) {
double mySum = 0;
// First partition vector at larger bound
std::nth_element(x.begin(), x.begin() + upper, x.end());
// Now create partition of above at lower bound
std::nth_element(x.begin(), x.begin() + lower, x.begin() + upper);
std::vector<int>::iterator it, itEnd = x.begin() + upper;
for (it = x.begin() + lower; it <= itEnd; it++)
mySum += *it;
return mySum;
}
这是用于测试的主要功能，我可能会添加一些粗糙的功能：
int main() {
std::vector<int> v(200001);
std::random_device rd;
std::mt19937 gen(rd());
std::iota(v.begin(), v.end(), -100000);
std::shuffle(v.begin(), v.end(), gen);
// random-sample without replacement
std::vector<int> randVec(v.begin(), v.begin() + 100000);
int val1, val2, val3;
std::clock_t start_time, end_time;
start_time = clock();
for (std::size_t i = 0; i < 100; i++)
val1 = boundedSumBen(randVec, 49900, 50100);
end_time = clock();
std::cout << "time taken on sample w/o rep std::nth_element : " <<
end_time - start_time << std::endl;
start_time = clock();
for (std::size_t i = 0; i < 100; i++)
val2 = boundedSumJoe(randVec, 49900, 50100);
end_time = clock();
std::cout << "time taken on sample w/o rep indexing method by Joe : " <<
end_time - start_time << std::endl;
start_time = clock();
for (std::size_t i = 0; i < 100; i++)
val3 = boundedSumOP(randVec, 49900, 50100);
end_time = clock();
std::cout << "time taken on sample w/o rep naive approach with std::sort : " <<
end_time - start_time << std::endl;
std::cout << "All functions on sample w/o rep return the same value of : " <<
val1 << ", " << val2 << ", and " << val3 << std::endl;
// Now we test a random sample with replacement
std::uniform_int_distribution<int> distribution(-100000, 100000);
for (std::size_t i = 0; i < 100000; i++)
randVec[i] = distribution(gen);
start_time = clock();
for (std::size_t i = 0; i < 100; i++)
val1 = boundedSumBen(randVec, 9900, 10100);
end_time = clock();
std::cout << "time taken on sample with rep std::nth_element : " <<
end_time - start_time << std::endl;
start_time = clock();
for (std::size_t i = 0; i < 100; i++)
val2 = boundedSumJoe(randVec, 9900, 10100);
end_time = clock();
std::cout << "time taken on sample with rep indexing method by Joe : " <<
end_time - start_time << std::endl;
start_time = clock();
for (std::size_t i = 0; i < 100; i++)
val3 = boundedSumOP(randVec, 9900, 10100);
end_time = clock();
std::cout << "time taken on sample with rep naive approach with std::sort : " <<
end_time - start_time << std::endl;
std::cout << "All functions on sample with rep return the same value of : " <<
val1 << ", " << val2 << ", and " << val3 << std::endl;
std::cout << "Number of unique elements in vector with replacement "
<< std::set<int>(randVec.begin(), randVec.end()).size()
<< std::endl;
return 0;
}
和我的计算机上的结果*(我正在使用clang++(：
time taken on sample w/o rep std::nth_element : 109925
time taken on sample w/o rep indexing method by Joe : 110162
time taken on sample w/o rep naive approach with std::sort : 581368
All functions on sample w/o rep return the same value of : 38849, 38849, and 38849
time taken on sample with rep std::nth_element : 93542
time taken on sample with rep indexing method by Joe : 102780
time taken on sample with rep naive approach with std::sort : 517273
All functions on sample with rep return the same value of : -16069147, -16069147, and -16069147
Number of unique elements in vector with replacement 78605
您可以看到，在速度和通用性方面，采用@Benvoigt提供的std::nth_element都优越，而索引方法仍然比幼稚的方法快得多。
- 这是IDEONE的结果(运行
gcc(。