資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++ 實現旋轉排序陣列中的最小值查詢
假設有一個已排序的陣列，該陣列在某個未知的樞軸點進行了旋轉。我們需要找到該旋轉陣列中的最小值。例如，如果陣列為 [3,4,5,1,2]，則輸出為 1。
為了解決這個問題，我們將遵循以下步驟：
- low := 0，high := 陣列的最後一個索引，n := 陣列的大小，ans := 無窮大
- 當 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 findMin(vector<int>& arr) {
int low = 0;
int high = arr.size() - 1;
int n = arr.size();
int ans = INT_MAX;
while(low <= high){
int mid = low + (high - low) / 2;
if(arr[low] < arr[mid]){
ans = min(ans, arr[low]);
low = mid + 1;
} else if(arr[high] > arr[mid]) {
ans = min(ans, arr[mid]);
high = mid - 1;
} else if(low == mid) {
ans = min(ans, arr[low]);
low = mid + 1;
} else if(high == mid) {
ans = min(ans, arr[high]);
high = mid - 1;
}
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {15,35,85,96,5,6,8,12};
cout << ob.findMin(v);
}輸入
[15,35,85,96,5,6,8,12]
輸出
5
更新於：2020年5月4日
瀏覽量：116
廣告