資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++實現旋轉排序陣列中的最小值
假設我們有一個已排序的陣列，現在它在某個樞軸點旋轉了。樞軸點事先未知。我們必須找到該陣列中的最小元素。例如，如果陣列是[4,5,5,5,6,8,2,3,4]，則最小元素是2。
為了解決這個問題，我們將遵循以下步驟：
定義一個名為search()的方法，它接受arr、low和high作為引數。
如果low = high，則返回arr[low]。
mid := low + (high – low) / 2
ans := inf (無窮大)
如果arr[low] < arr[mid]，則ans := arr[low] 和 search(arr, mid, high) 的最小值
否則，如果arr[high] > arr[mid]，則ans := arr[mid] 和 search(arr, low, mid) 的最小值
否則，如果arr[low] = arr[mid]，則ans := arr[low] 和 search(arr, low + 1, high) 的最小值
否則，如果arr[high] = arr[mid]，則ans := arr[high] 和 search(arr, low, high - 1) 的最小值
返回ans
從主方法呼叫solve(nums, 0, nums的大小 – 1)
示例
讓我們看看下面的實現，以便更好地理解：
#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 = INT_MAX;
if(arr[low] < arr[mid]){
ans = min(arr[low], search(arr, mid, high));
}
else if (arr[high] > arr[mid]){
ans = min(arr[mid], search(arr, low, mid));
}
else if(arr[low] == arr[mid]){
ans = min(arr[low], search(arr, low + 1, high));
}
else if(arr[high] == arr[mid]){
ans = min(arr[high], search(arr, low, high - 1));
}
return ans;
}
int findMin(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.findMin(v));
}輸入
[4,5,5,5,6,8,2,3,4]
輸出
2
更新於：2020年5月26日
262 次瀏覽
廣告