c++ - 多个数组段的最小平均值

Question

给定一个数组 A，我想找到一个段的第一个索引，其中所选段的平均值是其他段中最小的。

Example: A = {1, 1, 3, 4, 5, 6, 7}
segment (1,2) = {1,1} ==> avg = 1+1/2 = 1
segment (1,3) = {1,1,3} ==> avg = 1+1+3/3 = 1.6
etc.. 
________________________________________________
input: {1, 1, 3, 4, 5, 6, 7}
output: 1

解释:最小平均值为 1 因此输出应该是该段 (1,2) 的第一个索引，在本例中为:1。

我当前的代码如下所示:

int getIndex(vector<int> A) 
{
    if (A.size() <= 2) return 0; /*if array is a single segment then index:0 is the answer.*/

    vector<int> psums; psums.push_back(A[0]);

    for(size_t i =1; i< A.size(); i++)
    {
        psums.push_back(psums[i-1] + A[i]);
    }

    float min = 1111111111; /*assuming this is a max possible numb*/
    int index;
    float avg;

    for(size_t i =1; i< psums.size(); i++)
    {
        for(size_t j = 0; j < i; j++)
        {
            avg = (float)((psums[i] - psums[j]) / (i-j+1));
            if (min > std::min(min, avg))
            {
                min = std::min(min, avg);
                index = j;
            }
        }
    }
    return index;
}

此代码返回不正确的值。想法？

Answer 1

好的，我有一些时间，所以这是您希望寻找的代码(希望它也能编译——我没有机会在发布它之前测试它，所以给稍后我会检查几分钟——好的，现在用 gcc-4.7.2 编译):

#include<vector>
#include<tuple>
#include<functional>
#include<algorithm>
#include<iostream>
#include <numeric> 

size_t getIndex(const std::vector<int>& A) //pass by const ref instead of by value!

{
    size_t n=A.size();
    //define vector to store the averages and bounds
    std::vector<std::tuple<size_t, size_t, double> > store;

    for(size_t iend=0;iend<n;++iend)
        for(size_t ibegin=0;ibegin<iend;++ibegin)  //changed from <= to < as segments need to have length >=2
        {
             //compute average: sum all elements from ibegin to iend to 0.0, cast to double and divide by the number of elements
             double average=static_cast<double>(std::accumulate(A.begin()+ibegin, A.begin()+iend,0.0))/(iend-ibegin+1);

             //store the result with bounds
             store.push_back(std::make_tuple(ibegin,iend,average));
        }

    //define lambda which compares the tuple according to the third component
    auto compare_third_element=[](const std::tuple<size_t,size_t,double> &t1, const std::tuple<size_t,size_t,double> &t2){return std::get<2>(t1)<std::get<2>(t2);};

    //now find the iterator to the minimum element
    auto it=std::min_element(store.begin(),store.end(),compare_third_element);

    //print range
    //std::cout<<"("<<std::get<0>(*it)<<","<<std::get<1>(*it)<<")"<<std::endl;
    return std::get<0>(*it);
}

int main()
{
    std::vector<int> A={1,1,2,3,4,5,6,7};
    std::cout << getIndex(A);
    return 0;
}

注意:可能有不止一个片段产生最小平均值。对于上面的示例，该函数在屏幕上打印段 (0,0)，因为它包含最小元素 1。如果您想获得您正在寻找的范围，请使用 std::nth_element 访问下一个条目，或更改比较函数(例如，给较长的元组更高的优先级)。