数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++程序：查找旋转列表中的最大数
假设有一个已排序的数组，该数组在某个未知的枢轴点被旋转。我们需要找到该旋转数组中的最大值。例如，如果数组为[3,4,5,1,2]，则输出为5。
为了解决这个问题，我们将遵循以下步骤：
low := 0，high := 数组的最后一个索引，n := 数组大小，ans := 0
当 low <= high 时
mid := low + (high - low)/2
如果 arr[low] < arr[mid]，则 ans := ans 和 arr[low] 中的最大值，low := mid + 1
否则，如果 arr[high] > arr[mid]，则 ans := ans 和 arr[mid] 中的最大值，high := mid – 1
否则，如果 low = mid，则 ans := ans 和 arr[low] 中的最大值，low := mid + 1
否则，如果 high = mid，则 ans := ans 和 arr[high] 中的最大值，high := mid - 1
返回 ans
让我们来看下面的实现来更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int search(vector <int>& arr, int low, int high){
if(low == high){
return arr[low];
}
int mid = low + (high - low) / 2;
int ans = 0;
if(arr[low] < arr[mid]){
ans = max(arr[low], search(arr, mid, high));
}
else if (arr[high] > arr[mid]){
ans = max(arr[mid], search(arr, low, mid));
}
else if(arr[low] == arr[mid]){
ans = max(arr[low], search(arr, low + 1, high));
}
else if(arr[high] == arr[mid]){
ans = max(arr[high], search(arr, low, high - 1));
}
return ans;
}
int findMax(vector<int>& nums) {
return search(nums, 0, nums.size() - 1);
}
};
main(){
Solution ob;
vector<int> v = {4,5,5,5,6,8,2,3,4};
cout <<(ob.findMax(v));
}输入
[4,5,5,5,6,8,2,3,4]
输出
8
更新于：2020年10月8日
73 次查看
广告