c++ - 查找连续子数组的第二小总和

Question

我正在编写一个函数，除了数组的长度之外，它还接受一个指向动态分配的数组的指针。我试图找到它的连续子数组的第二小总和。

我一直在编写代码来计算数组中第二小的值，还有一段代码计算所有连续子数组的总和。我希望我能够将这两个部分“合并”在一起以获得我想要的最终结果，但我被卡住了。我真的很感激任何帮助。谢谢。

#include <iostream>
using namespace std;

int secondSmallestSum(int *numbers,int length) 
{

//Below shows the sum of all contiguous sub arrays.
for(i = 0; i<= length; ++i)
{
    int sum = 0;
    for(int j = i; j <= length; ++j)
    {
        sum+=*(numbers+j);

    }
}


//Below calculates the second smallest element in an array

int smallest, secondsmallest;

if (*numbers < *(numbers+1))
{
    smallest = *numbers;
    secondsmallest = *(numbers+1) ;
}
else {
  smallest = *(numbers+1) ;
  secondsmallest = *(numbers) ;
}
for (i = 2; i < length; i++) {
    if (*(numbers+i)  < smallest) 
    {
    secondsmallest = smallest;
    smallest = *(numbers+i);
    }
    else if (*(numbers+i) < secondsmallest) 
    {
        secondsmallest = *(numbers+i);
    }
}   

}

Answer 1

你可以这样做(当然你需要添加范围检查)。

#include <iostream>
#include <vector>
#include <algorithm>

int main(int argc, char** argv) {
  std::vector<int> v{3, 1, 4, 5, 6, 2};

  std::nth_element(v.begin(), v.begin() + 1, v.end());
  std::cout << "The second smallest element is " << v[1] << "\n";
}

注意:使用 nth_element 会改变 vector 中元素的顺序。