1 条题解
-
1
题解
方法1:遍历线性表
算法描述
很容易想到我们可以遍历整个线性表,根据山峰的定义,找到一个
nums[i] > nums[i - 1] and nums[i] > nums[i + 1]
的元素就行了。代码
// C++ #include <bits/stdc++.h> using namespace std; vector<int> arr; int n; int tmp; int main() { scanf("%d", &n); while (n--) { scanf("%d", &tmp); arr.push_back(tmp); } for (int i = 0; i < arr.size(); i++) if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) { printf("%d", i); return 0; } }
复杂度分析
空间复杂度: 时间复杂度:
方法2:二分查找
思路与算法
很显然,这样的查找题目可以用二分来解决。思路同上。
代码
#include <bits/stdc++.h> using namespace std; int findIndexInMountain(vector<int>& arr) { int n = arr.size(); int l = 1, r = n - 2, ans = 0; while (l <= r) { int mid = (l + r) >> 1; if (arr[mid] > arr[mid + 1]) { ans = mid; r = mid - 1; } else l = mid + 1; } return ans; } vector<int> arr; int n; int tool; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &tool); arr.push_back(tool); } tool = findIndexInMountain(arr); printf("%d", tool); return 0; }
复杂度分析
时间复杂度: 空间复杂度:
- 1
信息
- ID
- 16
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 3
- 已通过
- 1
- 上传者