向量中两个最小正数的和

Question

我创建了一个函数 sumOfTwoSmallestNumbers()，它接受一个整数向量（仅包含正值），它 returns 存储在该向量中的两个最小正数之和。不幸的是，我的函数在一些测试用例中失败了（我无权访问这些测试用例的输入）。请帮助我找出代码中的错误。 注意：向量总是至少包含 4 个正值

#include <iostream>
#include <vector>

using namespace std;

long sumOfTwoSmallestNumbers (vector<int> numbers)
{
  long int sum = 0;
  long int min1 = numbers[0];
  int position;
  for (unsigned long int i = 0; i < numbers.size(); i++){ 
    if (numbers[i] < min1){
      min1 = numbers[i];
      position = i;
    }
  }
  numbers.erase(numbers.begin() + position - 1);
  long int min2 = numbers[0];
  for (unsigned long int i = 0; i < numbers.size(); i++){ 
    if (numbers[i] < min2){
      min2 = numbers[i];
    }
  }
  sum = min1 + min2;
  return sum;
}

逻辑： 我试图首先找到最小值并将其存储在变量中，然后从向量中删除该值。之后，我再次搜索向量中的最小值并将其存储在一个变量中。最后，我将两个值相加并返回了总和。

Answer 1

嗯，这是一个 two-liner...

std::sort(vec.begin(),vec.end());
auto sum = vec.at(0) + vec.at(1);

希望对您有所帮助

警告：它不会跳过负数，但作为 OP 的学习练习已被遗漏。

Answer 2

你怎么看这个：


// Simple function that will swap smallest with next_smallest
// if smallest > next_smallest. Returns true if a swap happened
bool TwoItemSort(int& smallest, int& next_smallest)
{
    if (next_smallest < smallest)
    {
        int tmp = smallest;
        smallest = next_smallest;
        next_smallest = tmp;
        return true;
    }
    return false;
}

long sumOfTwoSmallestNumbers(const vector<int>& numbers)
{
    if (numbers.size() < 2)
    {
        return 0;
    }

    int smallest = numbers[0];
    int nextsmallest = numbers[1];

    TwoItemSort(smallest, nextsmallest);

    for (size_t i = 2; i < numbers.size(); i++)
    {
        int value = numbers[i];
        if (TwoItemSort(nextsmallest, value))
        {
            TwoItemSort(smallest, nextsmallest);
        }
    }

    return smallest + nextsmallest;
}

Answer 3

您的代码有几个问题：

如果vector中最小的数字是第一个，position将未初始化并导致UB（未定义行为）。
如果你根据需要将 position 初始化为 0，那么如果 vector 中的最小数字是第一个，这一行 numbers.erase(numbers.begin() + position - 1) 将尝试使用迭代器在 numbers.begin() 之前。这是无效的。

我下面的解决方案只跟踪 smallest 和 secondSmallest，根本不需要修改 vector（因此我可以通过 const& 传递它）。也只需要遍历一次vector（复杂度为O(n)）。

#include <iostream>
#include <vector>
#include <assert.h>

long sumOfTwoSmallestNumbers(std::vector<int> const & numbers)
{
    assert(numbers.size() >= 4);   // The OP specified that in the question.
    int smallest =       (numbers[0] < numbers[1]) ? numbers[0] : numbers[1];
    int secondSmallest = (numbers[0] < numbers[1]) ? numbers[1] : numbers[0];
    for (size_t i = 2; i < numbers.size(); ++i)
    {
        if (numbers[i] < smallest)
        {
            // Need to update both:
            secondSmallest = smallest;
            smallest = numbers[i];
        }
        else if (numbers[i] < secondSmallest)
        {
            // Need to update only second:
            secondSmallest = numbers[i];
        }
    }
    return (smallest + secondSmallest);

}

int main()
{
    std::vector<int> v = { 1,4,7,2 };
    auto s = sumOfTwoSmallestNumbers(v);
    std::cout << "sumOfTwoSmallestNumbers: " << s << std::endl;
    return 0;
}

输出：

sumOfTwoSmallestNumbers: 3

旁注：最好避免 using namespace std - 请参阅此处 Why is "using namespace std;" considered bad practice?。

Answer 4

#include <bits/stdc++.h>

using namespace std;

int sumOfSmallestPositive(vector<int> arr);

int main()
{

     vector<int> arr{-8,-24,14,-56,-1,5,87,12,-10,11};
     cout<<sumOfSmallestPositive(arr);
     return 0;
}


int sumOfSmallestPositive(vector<int> arr)
{
    sort(arr.begin(),arr.end());
    pair<int,int> p;
    for(int i=0;i<arr.size();i++)
    {
        if(arr[i]>0)
        {
            p.first=arr[i];
            p.second=0;
            if(i+1<=arr.size()-1)
                p.second=arr[i+1];
            break;
        }
    }
    return p.first +p.second;  //return 5+11=16
}

向量中两个最小正数的和

Sum of the two lowest positive numbers in a vector

c++

sum

vector