c++实现,时间复杂度为O(N):找到石头对。有N个石头,标号为[0,N-1]。我们知道每个石头的重量,不一定为整数。我们想要找到一对石头,即2个石头,它们的重量差为D,D不一定为整型。
时间: 2023-10-06 19:06:40 浏览: 69
我们可以利用哈希表来解决这个问题。首先遍历所有石头,将它们的重量作为键,对应的索引作为值存储在哈希表中。接着再次遍历所有石头,对于每一个石头,我们只需要在哈希表中查找是否存在重量为“该石头重量+D”的石头即可。如果存在,那么我们就找到了一对符合条件的石头,直接返回它们的索引即可。
时间复杂度分析:遍历所有石头需要O(N)的时间,对于每个石头,哈希表查找需要O(1)的时间,因此总时间复杂度为O(N)。
以下是C++代码实现:
```c++
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
vector<int> findStonePair(vector<double>& stones, double diff) {
int n = stones.size();
unordered_map<double, int> m;
for (int i = 0; i < n; i++) {
m[stones[i]] = i;
}
for (int i = 0; i < n; i++) {
double target = stones[i] + diff;
if (m.find(target) != m.end() && m[target] != i) {
return {i, m[target]};
}
}
return {-1, -1};
}
int main() {
vector<double> stones = {1.2, 3.4, 5.6, 2.2, 4.4};
double diff = 2.0;
vector<int> res = findStonePair(stones, diff);
if (res[0] == -1 && res[1] == -1) {
cout << "No such stone pair!" << endl;
} else {
cout << "Stone pair found: " << res[0] << " " << res[1] << endl;
}
return 0;
}
```
阅读全文