c++ - 降低程序的复杂度

Question

下面是查找总和为 3 的对的程序。

例如:

INPUT : 0,3,5,1,2,4
OUTPUT: 0,3,1,2.

这意味着它应该返回所有总和等于 3 的对。

但是我想降低这个程序的时间复杂度。现在我正在使用两个嵌套的 for 循环。

谁能提出一个更好的方法来降低时间复杂度。

#include<iostream>
#include <vector>
using namespace std;

void main()
{
   vector<int> v;
   vector<int> r;
   int x;

   cout << "Enter the elements";

   for(int i = 0; i < 6; i++)
   {
       cin >> x;
       v.push_back(x);
   }

   for(int i = 0 ; i < v.size() - 1; i++)
   {
       for(int j = i + 1; j < v.size(); j++)
       {
          if(v[i] + v[j]  == 3)
          {
              r.push_back(v[i]);
              r.push_back(v[j]);
          }
       }
   }

   cout << "\noutput\n";

   for(int i = 0 ; i < r.size(); i++)
   {
       cout<<r[i]<<"\n";
   }

}

Answer 1

我会做两个准备步骤；首先，消除所有大于 3 的数字，因为它们不属于任何有效对。这降低了第二步的复杂性。其次，对剩余的数字进行排序，这样一次遍历就可以找到所有结果。

遍历从排序数组的两端接近对；如果找到一对，则可以缩小两个界限；如果当前结尾的总和大于 3，则只有一个边界变窄。

运行时复杂度为 O(N logN)，其中 N 是元素的数量 <= 3； O(N logN) 基本上来自于排序；两次单次遍历将不计入较大的 N。

int main(int argc, char* argv[]) {

    const int N = 3;

    std::vector<int> input{ 0,3,5,1,2,4};
    std::vector<int>v(input.size());
    int t=0;
    for (auto i : input) {
        if (i <= N) {
            v[t++]=i;
        }
    }
    std::sort (v.begin(), v.end());

    long minIdx = 0;
    long maxIdx = v.size()-1;
    while (minIdx < maxIdx) {
        int minv = v[minIdx];
        int maxv = v[maxIdx];
        if (minv+maxv == 3) {
            cout << minv << '+' << maxv << endl;
            minIdx++;maxIdx--;
        }
        else
            minIdx++;
    }
    return 0;
}