資料結構
網路
關係型資料庫管理系統 (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 次檢視
廣告