給定一個整數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 Pair 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）