首页 文章

给定一个整数数组,找到整数之和,它将在给定位置之间的排序数组中

提问于
浏览
2

我必须为我的任务找到最好的算法(复杂性) .

输入:索引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 回答

  • 5

    看一下 std::nth_element 算法,该算法将"first N"与"elements past N"分开,而无需在两个分区内进行额外的排序工作 .

    为了您的目的,您需要两次调用 nth_element . 第二个调用将在第一步中创建的一个分区上,而不是整个数组 . 最后,您将有三个分区:

    • 元素少于您需要的元素

    • 您需要的元素

    • 元素大于你需要的元素

    它通常在线性时间内完成,尽管最坏情况仍为O(N lg N)

  • 1

    这是一种比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提供的解决方案的强大功能 . 首先,这是OP的实现和使用 std::nth_element 的实现 .

    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 )的结果 .

相关问题