c++实现:找到石头对。有N个石头,标记为[0,N-1]。我们知道每个石头的重量。我们想要找到一对石头,即两个石头,它们的重量差为D。问题A:正式描述问题,以清楚地定义问题而不含糊。例如:编写一个函数F,其输入是...函数的输出是...这个问题可能比你想象的要难,请仔细思考。问题B:1.编写你在问题A中描述的函数。2.你的算法的空间复杂度是多少?时间复杂度是多少?3.你能实现O(N)的时间复杂度和空间复杂度吗?如果可以,请实现它。4.编写一个测试程序来测试你的函数。a.请列出你想要测试的所有边界情况。b.如何验证函数可以正确处理这些边界情况?你能以更系统化的方式完成吗?问题C(可选)与原始问题B相同,但这次我们想要找到所有重量差为D的石头对。请注意,对(1,4)和对(4,1)被视为同一个对,因此只需要返回一个。你的算法的时间复杂度应为O(max(R,N)),其中R是结果对的数量,N是石头的数量。
时间: 2023-07-16 07:13:09 浏览: 72
问题A:
给定一个长度为N的石头数组,每个石头有一个对应的重量,找到一对石头,它们的重量差为D。编写一个函数,其输入为石头数组和D,输出为找到的石头对的下标。
函数F的输入:vector<int> stones, int D
函数F的输出:vector<int>,包含找到的石头对的下标,如果没有找到,则返回空vector。
问题B:
1. 实现函数F,可以使用两个指针分别指向数组中的不同石头,然后根据它们的重量差是否为D来移动指针。具体实现详见代码。
2. 空间复杂度为O(1),时间复杂度为O(NlogN),其中N是石头的数量。时间复杂度来自于排序操作。
3. 可以实现O(N)的时间复杂度和O(N)的空间复杂度。具体实现也详见代码。
4. 测试程序如下:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> findStonePairs(vector<int>& stones, int D) {
vector<int> result;
sort(stones.begin(), stones.end());
int left = 0, right = 1;
while (right < stones.size()) {
int diff = stones[right] - stones[left];
if (diff == D) {
result.push_back(left);
result.push_back(right);
return result;
} else if (diff < D) {
right++;
} else {
left++;
}
}
return result;
}
vector<int> findStonePairsOptimized(vector<int>& stones, int D) {
vector<int> result;
unordered_map<int, int> stoneMap;
for (int i = 0; i < stones.size(); i++) {
int target = stones[i] - D;
if (stoneMap.count(target)) {
result.push_back(stoneMap[target]);
result.push_back(i);
return result;
}
stoneMap[stones[i]] = i;
}
return result;
}
void test() {
vector<vector<int>> testCases = {
{1, 3, 5, 6, 8, 10},
{2, 4, 6, 8, 10},
{5, 10, 15, 20},
{1, 1, 2, 3, 4, 5},
{1, 2, 3, 4, 5}
};
vector<int> testDiffs = {2, 2, 5, 0, 3};
vector<vector<int>> expectedResults = {
{0, 2},
{0, 2},
{0, 3},
{0, 1},
{0, 3}
};
for (int i = 0; i < testCases.size(); i++) {
auto pair = findStonePairs(testCases[i], testDiffs[i]);
auto optimizedPair = findStonePairsOptimized(testCases[i], testDiffs[i]);
if (pair != expectedResults[i] || optimizedPair != expectedResults[i]) {
cout << "Test case " << i << " failed." << endl;
cout << "Expected: " << expectedResults[i][0] << ", " << expectedResults[i][1] << endl;
cout << "Found: " << pair[0] << ", " << pair[1] << endl;
cout << "Optimized Found: " << optimizedPair[0] << ", " << optimizedPair[1] << endl;
return;
}
}
cout << "All test cases passed." << endl;
}
int main() {
test();
return 0;
}
```
a. 边界情况包括:
- 空数组
- 只有一个元素的数组
- 所有元素都相同的数组
- 所有元素都比D小的数组
- 所有元素都比D大的数组
- 无法找到重量差为D的石头对的数组
b. 验证方法:使用测试程序运行所有边界情况。如果所有测试用例都通过,则可以保证函数能够正确处理所有边界情况。如果需要更系统化的测试,可以使用更多的测试用例,例如随机生成的测试用例。
问题C:
解决这个问题的一种方法是使用哈希表来记录每个石头的位置,并在查找时使用哈希表来查找是否存在一个石头的重量等于另一个石头的重量加上D。具体实现详见以下代码。
```c++
vector<vector<int>> findAllStonePairs(vector<int>& stones, int D) {
vector<vector<int>> result;
unordered_map<int, int> stoneMap;
for (int i = 0; i < stones.size(); i++) {
int target = stones[i] - D;
if (stoneMap.count(target)) {
result.push_back({stoneMap[target], i});
}
stoneMap[stones[i]] = i;
}
return result;
}
```
时间复杂度为O(max(R, N)),其中R是结果对的数量,N是石头的数量,空间复杂度为O(N)。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)