一个100*100的网格,网格中有随机0-100数字,找出其中的峰值,返回对应网格下标,QT
时间: 2024-03-26 10:40:32 浏览: 54
好的,以下是一个可能的解法:
1. 在 QT Creator 中创建一个新的空项目
2. 在项目目录下创建一个名为 `PeakFinder` 的文件夹,并在里面创建两个文件:`peakfinder.h` 和 `peakfinder.cpp`
3. 打开 `peakfinder.h`,输入以下代码:
```cpp
#ifndef PEAKFINDER_H
#define PEAKFINDER_H
#include <vector>
#include <utility>
class PeakFinder {
public:
static std::pair<int, int> findPeak(const std::vector<std::vector<int>>& grid);
};
#endif // PEAKFINDER_H
```
4. 打开 `peakfinder.cpp`,输入以下代码:
```cpp
#include "peakfinder.h"
std::pair<int, int> PeakFinder::findPeak(const std::vector<std::vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
int left = 0, right = m - 1;
while (left <= right) {
int mid = (left + right) / 2;
int max_row = 0;
for (int i = 0; i < n; i++) {
if (grid[i][mid] > grid[max_row][mid]) {
max_row = i;
}
}
if ((mid == 0 || grid[max_row][mid] >= grid[max_row][mid - 1])
&& (mid == m - 1 || grid[max_row][mid] >= grid[max_row][mid + 1])) {
return std::make_pair(max_row, mid);
} else if (mid > 0 && grid[max_row][mid - 1] > grid[max_row][mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return std::make_pair(-1, -1); // 没有峰值
}
```
5. 在 QT Creator 中创建一个名为 `main.cpp` 的新文件,并输入以下代码:
```cpp
#include <iostream>
#include <vector>
#include <cstdlib>
#include "peakfinder.h"
using namespace std;
int main() {
vector<vector<int>> grid(100, vector<int>(100));
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
grid[i][j] = rand() % 101;
}
}
pair<int, int> peak = PeakFinder::findPeak(grid);
if (peak.first == -1) {
cout << "No peak found" << endl;
} else {
cout << "Peak found at (" << peak.first << ", " << peak.second << ")" << endl;
}
return 0;
}
```
6. 在 QT Creator 中编译并运行程序,看看能否正确输出峰值的下标。
这个解法和之前的 C++ 解法是一样的,只是把代码分成了多个文件,并使用了一个类来包装函数。
阅读全文