c++ - 删除两个相邻元素并用 vector 中的单个元素替换它们

Question

所以我想从一个 vector 中找到两个相邻的元素(最后一个和第一个是相邻的)，使得它们的总和最小，然后用单个元素替换它们=它们的总和。应该这样做，直到剩下一个元素。

我编写了一个函数来查找最小的相邻对并返回较低的索引。然后将该索引之后的所有元素移动一个位置并使用 a.resize(n-1)。代码不起作用，我想主要问题是比较最后和第一个。

int index(vector<int> a)
{
int idx=0; int ans=100; int sum=0;
for (int i = 0; i < a.size(); ++i)
{
    sum=a[i]+a[i+1];
    if(sum<ans)
        idx=i;
}
if(a[0]+a[a.size()-1]<ans)
    idx=a.size()-1;
return idx;
}
//in main function
for (int i = 0; i < n-1; ++i)
    {
        int idx=index(a);
        if(idx==a.size()-1)
            {a[0]=a[0]+a[a.size()-1];
                ans+=a[0]+a[a.size()-1];
                a.pop_back();
            }
        else
        {
            a[idx]=a[idx]+a[idx+1];
            ans+=a[idx]+a[idx+1];
            a.erase(a.begin()+idx-1);

        }

Answer 1

这是我的解决方案。

由于数组是圆形的，数组中的每个元素都可能是相邻对中总和最小的第一个元素。

因此请考虑索引 i 处的每个元素, 及其索引对 j这是(i + 1) % n找到最小的一对。 ...哪里 n是 vector 中的当前元素数。 % n将处理数组的环绕和循环性质。当i是最后一个元素 ( n - 1 )，然后是 j将是第一个元素 ( 0 )。

一旦指数i和 j已确定最小对中的一个，将两个元素中的一个替换为总和，并且 erase另一个。您应用的约定将决定第一个元素和最后一个元素的总和是放在 vector 的开头还是结尾。

重复此操作，直到只剩下一个元素。

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

// Just a handy function to display the vector.
void print(std::vector<int> const& input)
{
    std::copy(input.begin(), input.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
}

int main() {
    std::vector<int> vec{ 3, 1, 4, 1, 5, 9, 2 }; // some example input data

    print(vec);
    while (vec.size() > 1) {
        // Find the smallest pair of adjacent elements.
        size_t min_i = 0;
        size_t min_j = 1;
        int min_sum = vec[0] + vec[1];
        for (size_t i = 1; i < vec.size(); ++i) {
            size_t j = (i + 1) % vec.size();
            int sum = vec[i] + vec[j];
            if (sum < min_sum) {
                min_i = i;
                min_j = j;
                min_sum = sum;
            }
        }
        // Replace element i with the sum.
        vec[min_i] = min_sum;
        // Erase element at j;
        vec.erase(vec.begin() + min_j);

        print(vec);
    }
}

输出:

3 1 4 1 5 9 2
4 4 1 5 9 2
4 5 5 9 2
5 5 9 6
10 9 6
10 15
25

---

编辑:OP 要求显示他们出错的地方。

至于你的代码，有太多的问题和危险的做法。 :(

首先，请记住索引 [n]如果有 n 则无效数组中的元素。具有 n 的数组的有效索引元素是 0通过n-1包括的。所以访问[i]和 [i+1]什么时候i == n-1是一个缓冲区溢出错误，因为您正在访问元素 n-1 (最后一个)和n-1 + 1 , 倒数一个。

您计算最小总和的代码不正确，因为它更新了 sum (应该是本地的)但不是 ans .编写较小的函数并为这些函数编写单元测试。如果您编写了一个函数来计算数组对的最小值，您会发现它甚至无法通过最基本的单元测试。您编写的代码未计算最小值。

给定一个至少包含一个元素的数组，找到最小值的索引及其索引通常如下所示:

int min_val = a[0];
int min_index = 0;
for (int i = 1; i < n; ++i) {
   if (a[i] < min_val) {
      min_val = a[i];
      min_index = i;
   }
}

100不是一个合适的初始最小值(如果这是你想要的)。类似 MAX_INT 的值更好。 std::numerical_limits<int>::max()对于现代 C++ 来说更好。

你递增 ans在一个循环中，它保留了上一个循环中以前使用的值。另外，ans以后不会在您的程序中使用。我建议您明智地对局部变量应用最严格的范围。

您通过编写带有逻辑检查的重复代码来特殊封装您的环绕，这增加了您引入错误的机会，而您应该使用取模运算符将代码路径提炼为单个路径处理环绕和标称邻接情况的执行。

最后，您的算法所做的只是计算数组的总和并将其存储在单个元素中。使用 erase 一次删除一个元素的方法与直接求和计算相比，这是一种性能灾难。我很尊重你的请求，因为你没有透露你的“理由”，所以我仍然觉得在这一点上非常不合理和可疑，除非这只是一个学习练习。