c++实现,时间复杂度为O(N):找到石头对。有N个石头,标号为[0,N-1]。我们知道每个石头的重量,不一定为整数,且石头的重量可能相同。我们想要找到一对石头,即2个石头,它们的重量差为D,D不一定为整型。
时间: 2023-10-03 11:11:00 浏览: 117
我们可以使用一个 unordered_set 来存储已经遍历过的石头的重量,然后遍历每个石头,判断是否存在一个石头的重量等于当前石头的重量加上 D 或者减去 D。如果存在这样的石头,则说明找到了一对符合条件的石头。
具体实现可以参考下面的代码:
```c++
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
pair<int, int> findStonePair(vector<double>& stones, double diff) {
unordered_set<double> stoneSet;
for (auto stone : stones) {
if (stoneSet.count(stone + diff)) {
return {stone + diff, stone};
}
if (stoneSet.count(stone - diff)) {
return {stone - diff, stone};
}
stoneSet.insert(stone);
}
return {-1, -1};
}
int main() {
vector<double> stones = {1.5, 2.3, 3.7, 4.2, 5.0};
double diff = 1.2;
auto stonePair = findStonePair(stones, diff);
if (stonePair.first == -1 && stonePair.second == -1) {
cout << "No stone pair found!" << endl;
} else {
cout << "Stone pair found: (" << stonePair.first << ", " << stonePair.second << ")" << endl;
}
return 0;
}
```
该算法的时间复杂度为 O(N),因为我们只需要遍历一遍石头列表,并且使用 unordered_set 来判断石头是否存在的时间复杂度是 O(1)。
阅读全文