3

我正在尝试使用 C++ 中的排序向量来实现 2-SUM 算法的变体。任务是读入一个包含 10^6 个整数的文件，并计算总和为 t 的不同整数（x 和 y）的数量，其中 t 在区间 [-10000, 10000] 内。我已经在几个测试用例上测试了我的代码，它似乎正在工作，但我没有得到编程任务的正确答案。这是针对 Coursera 算法：设计和分析课程的。因此，此作业不会获得任何官方学分。我会很感激任何帮助。你可以在下面找到我的代码。

/*
 * TwoSums.cpp
 * Created on: 2013-08-05
 * 
 * Description: Implemented a variant of the 2-SUM algorithm for sums between -10000 and 10000.
 * The task was to compute the number of target values t in the interval [-10000,10000]
 * (inclusive) such that there are distinct numbers x,y in the input file (./HashInt.txt)
 * that satisfy x+y=t. The input file was taken from the Algorithms: Design and Analysis course
 * taught by Tim Roughgarden on Coursera.
 * 
 */

#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <set>

#define LOWER -10000
#define HIGHER 10000

using namespace std;

const char* inputfile = "./HashInt.txt";

/*
 * Precondition: The inputfile is a file that contains integers, both 
 *               positive and negative. Each line contains an integer.
 * 
 * Postcondition: Every number in the file will be stored in vector V. 
 */

int ReadFile(vector<long>& V) {
    std::string line;
    std::ifstream infile;
    infile.open(inputfile);

    if(infile.fail())
    {
        cout << "Problem opening file.";
        return -1;
    }

    while (getline(infile, line)) {
        istringstream iss(line);
        long a;
        iss >> a;
        V.push_back(a);
    }

    return 0;
}

/*
 * Precondition: V is a sorted vector of integers
 * 
 * Postcondition: The number of target values (t) in the interval
 * [-10000,10000] will be displayed in stdout such that there
 * are distinct numbers x,y in the input file that satisfy x+y=t.
 */

void TwoSum (const vector<long>& V) {
    vector<long>::iterator x;
    vector<long>::iterator y;
    unsigned long count = 0;

    for (int i = LOWER; i <= HIGHER; ++i) {
        x = V.begin();
        y = V.end()-1;

        while (x != y) {
            long sum = *x + *y;
            if (sum == i) {
                count++;
                break;
            }

            else if(sum < i) {
                x+=1;
            }

            else {
                y-=1;
            }
        }
    }
    cout << "Count is: " << count << endl;
}

int main () {

    // Read integers, store in vector
    vector<long>V;
    if (ReadFile(V) < 0) return -1;

    // Erase duplicate numbers and sort vector
    set<long> s;
    unsigned long size = V.size();
    for( unsigned long i = 0; i < size; ++i ) s.insert( V[i] );
    V.assign(s.begin(),s.end() );

    // Implement 2-SUM algorithm for numbers between -10000 and 10000
    TwoSum(V);

    return 0;
}
4

2 回答 2

0

该程序不要求用户输入以用作“t”的值。所以我假设您不希望 xy 对的数量加起来为特定的 t。您的程序会遍历 't' 的所有可能值，并查看是否有 xy 对相加，然后转到 't' 的下一个值。

于 2013-08-06T11:22:01.480 回答
0

我相信您需要先对数据向量进行排序，然后再通过 LOWER 到 HIGHER 进行循环。因为，必须对数据进行排序以应用您使用 x 和 y 作为两个相反方向的迭代器实现的算法。

于 2015-08-21T18:36:38.400 回答