代码#include <iostream> #include <unordered_set> #include <algorithm> #include <vector> using namespace std; vector<pair<int, int>> findStonePairs(vector<int> &weights, int d) { unordered_set<int> stoneSet; vector<pair<int, int>> pairs; for (int i = 0; i < weights.size(); i++) { int weight = weights[i]; if (stoneSet.find(weight - d) != stoneSet.end()) { auto j = find(weights.begin(), weights.end(), weight - d) - weights.begin(); pairs.push_back({weights[j], weights[i]}); } if (stoneSet.find(weight + d) != stoneSet.end()) { auto j = distance(weights.begin(), find(weights.begin(), weights.end(), weight + d)); pairs.push_back({weights[j], weights[i]}); } stoneSet.insert(weight); } return pairs; } int main() { int d = 2; vector<int> weights = {1, 3, 3, 5, 4, 2, 7, 1}; vector<pair<int, int>> pairs = findStonePairs(weights, d); for (auto p : pairs) { cout << "[" << p.first << ", " << p.second << "]" << endl; } // for (auto p : pairs) // { // cout << "[" << weights[p.first] << ", " << weights[p.second] << "]" << endl; // } return 0; }的时间复杂度
时间: 2023-07-15 19:12:02 浏览: 51
这段代码的时间复杂度为 O(n^2),其中 n 为 weights 数组的长度。因为代码中使用了一个循环遍历 weights 数组,再在内部使用了两次 find 或 distance 函数查找 stoneSet 中是否存在特定的元素,这两个函数本质上也是一个循环遍历,因此总的时间复杂度就是 O(n^2)。
相关问题
#include <iostream> #include <vector> #include <algorithm>
#include <iostream> 是C++中的一个头文件,它包含了输入输出流的相关函数和对象,例如cout和cin。通过包含这个头文件,我们可以在程序中使用标准输入输出流来进行输入和输出操作。
#include <vector> 是C++中的一个头文件,它定义了一个名为vector的容器类模板。vector是一个动态数组,可以存储不同类型的元素,并且可以根据需要动态调整大小。
#include <algorithm> 是C++中的一个头文件,它包含了一些常用的算法函数,例如排序、查找、替换等。通过包含这个头文件,我们可以在程序中使用这些算法函数来对容器中的元素进行操作。
#include<iostream> #include<cstdio> using namespace std;是什么意思
#include<iostream> #include<cstdio> using namespace std; 是C++中的预处理指令,用于引入头文件和命名空间。
1. #include<iostream> 是引入iostream头文件,其中包含了输入输出流的定义,例如cout和cin等。
2. #include<cstdio> 是引入cstdio头文件,其中包含了C语言标准输入输出函数的定义,例如printf和scanf等。
3. using namespace std; 是使用std命名空间,std是C++标准库的命名空间,其中包含了很多常用的函数和类。
这些预处理指令的作用是为了在程序中能够使用输入输出流和标准库函数,使得程序更加方便和简洁。
相关推荐
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)