给定N个整数和整数y,确定N中是否存在两个元素,其绝对差值等于y

Question

我遇到了这个问题,我坚持这个.它说,

给定整数的集合N和整数Y,确定是否存在退出于N的绝对差等于y和同时打印这些数字的两个元素.该算法应该花费O(n lg n)时间.证明您的算法在O(n lg n)时间内运行的原因.例如,设N = 3,7,2,1,4,10 y = 1,N中有三对元素,其绝对差为1对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);
}

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)