给定一组N个整数和一个y，确定N中是否存在两个元素的绝对差等于y

Zohaib Aslam 发表于 Dev

佐伊卜·阿斯兰

我碰到了这个问题，我一直坚持下去。它说，

给定一组N个整数和一个y，确定N中是否存在两个绝对差等于y的元素，并打印这些数字。该算法应花费O（n lg n）时间。证明为什么算法要在O（n lg n）时间内运行。例如，假设N = 3，7，2，1，4，10 y = 1，则N中有三对元素的绝对差为1 Pair 1 = | 3-2 | = | -1 | = 1对2 = | 3 -4 | = | -1 | = 1对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);
}

萨沙

使用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

另一个算法：

排序元素（NlogN）
对于每个元素，请使用二进制搜索（每个搜索查询的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;
}