降低程序的复杂性
这是一个程序，以找到对的总和为3。
例如：
投入: 0,3,5,1,2,4 产出: 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";
}
}回答 4
Stack Overflow用户
发布于 2017-04-23 18:57:42
我将执行两个准备步骤；首先，消除所有大于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;
}Stack Overflow用户
发布于 2017-04-23 18:54:03
您正在搜索n元素中两个数字之间的所有组合，更确切地说，是那些加到特定值的组合。这是子集和问题的一个变体。
要实现这一点，您可以生成所有的组合，而不需要重复保存值的向量的索引。这里有一个如何做这个recursively的例子，这里是一个如何做它的例子，iteratively，只是为了获得一个想法，并可能使用它作为基准在您的情况下。
另一种方法是http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/和http://www.geeksforgeeks.org/backttracking-set-4-subset-sum/。
Stack Overflow用户
发布于 2017-04-23 18:38:46
我想你可以用地图在O(n)中解决这个问题。
public void printPairs(int[] a, int v)
{
map<int, int> counts = new map<int, int>();
for(int i = 0; i < a.length; i++)
{
if(map.count(a[i]) == 0)
{
map[a[i]] = 1;
}
else
{
map[a[i]] = map[a[i]] + 1;
}
}
map<int, int>::iterator it = map.begin();
while(it != map.end())
{
int v1 = it->second;
if (map.count(v - v1) > 0)
{
// Found pair v, v1
//will be found twice (once for v and once for v1)
}
}
}https://stackoverflow.com/questions/43574874
复制相似问题
腾讯云开发者
