c++ - 给定一个整数集合 N 和一个整数 y，判断 N 中是否存在绝对差等于 y 的两个元素

Question

我遇到了这个问题，我一直坚持这个问题。它说，

Given a set N of integers and an integer y, determine if there exit two elements in N whose absolute difference is equal to y and also print those numbers. The algorithm should take O(n lg n) time. Justify why your algorithm runs in O(n lg n) time. e.g. Let N= 3 , 7, 2, 1, 4, 10 y = 1 there are three pairs of elements in N whose absolute difference is 1 Pair 1 = |3 - 2| = |-1| = 1 Pair 2 = |3 - 4|= |-1| = 1 Pair 3 = |2 -1| = 1

我在 C++ 中按如下方式进行了尝试，但它并没有处理所有边界情况，例如在上面的示例中，如果 y=8，它不会打印任何内容，但它应该打印 (2,10)。

vector<int> printPairs(vector<int> N1, vector<int> N2, int y){
    int a = 0, b = 0;
    vector<int> result;
    while (a < N1.size() && b < N2.size()){
        if (N1[a] < N2[b]){
            result.push_back(N1[a]);
            if (abs(N1[a] - N2[b]) == y)
                cout << "(" << N1[a] << "," << N2[b] << ")" << endl;
            a++;
        }
        else {
            result.push_back(N2[b]);
            if (abs(N1[a] - N2[b]) == y)
                cout << "(" << N1[a] << "," << N2[b] << ")" << endl;
            b++;
        }
    }
    while (a < N1.size())
        result.push_back(N1[a++]);
    while (b < N2.size()){
        result.push_back(N2[b++]);
    }
    return result;
}
vector <int> getPairs(vector<int> N, int y){
    if (N.size() == 1)
        return N;
    vector <int> firstHalf = getPairs(vector<int>(N.begin(), N.begin() + N.size() / 2), y);
    vector <int> secondHalf = getPairs(vector<int>(N.begin() + ceil(N.size() / 2), N.end()), y);
    return printPairs(firstHalf, secondHalf, y);
}

Answer 1

使用 std::set 容器。

std::set::find() 的时间复杂度是 O(logN)。

调用 N 次 find() 花费 O(NlogN)。

代码示例:

#include <iostream>
#include <set>

int main() {
  std::set<int> values = {3, 7, 2, 1, 4, 10};
  int y = 1;
  for (int elem : values) {
    if (values.find(elem + y) != values.end()) {
      std::cout << elem << " " << elem + y << std::endl;
    }
  }
  return 0;
}

输出:

1 2
2 3
3 4

另一种算法:

1. 排序元素(NlogN)

2. 对每个元素使用二进制搜索(每个搜索查询的 logN)。

例子:

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

int main() {
  std::vector<int> values = {3, 7, 2, 1, 4, 10};
  int y = 1;
  std::sort(values.begin(), values.end());
  for (int i = 0; i + 1 < values.size(); ++i) {
    if (std::binary_search(
          values.begin() + i + 1, values.end(), values[i] + y)) {
      std::cout << values[i] << " " << values[i] + y << std::endl;
    }
  }
  return 0;
}

输出:

1 2
2 3
3 4

或者你可以通过使用两个指针的想法将步骤 2 简化为 O(N):

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

int main() {
  std::vector<int> values = {3, 7, 2, 1, 4, 10};
  int y = 1;
  std::sort(values.begin(), values.end());
  int l = 0, r = 0;
  for (int i = 0; i + 2 < 2 * values.size(); ++i) {
    if (r + 1 < values.size() &&
        values[r] - values[l] <= y) {
      ++r;
    } else {
      ++l;
    }
    if (values[l] + y == values[r]) {
      std::cout << values[l] << " " << values[r] << std::endl;
    }
  }
  return 0;
}

总复杂度将相同(但算法会快一点):O(NlogN) + O(N) = O(NlogN)