資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究在 C++ 中找出陣列中的區域性最小值
假設我們有一個包含 n 個元素的陣列 A。我們需要找到陣列的區域性最小值。在陣列 A 中，元素 A[x] 被認為是區域性最小值，如果它小於或等於其兩個相鄰元素。對於角元素，只考慮一個相鄰元素。如果有多個區域性最小值，則只返回一個。例如，如果陣列類似於 [9, 6, 3, 14, 5, 7, 4]，則區域性最小值可以為 3、5 和 4，因此此演算法只能返回其中一個。
為了解決這個問題，我們將遵循二分搜尋之類的邏輯。如果中間元素小於其左側和右側元素，則返回 mid，否則，如果大於了左側相鄰元素，則在左側可能存在一些區域性最小值，如果大於了右側元素，則在右側將存在一些區域性最小值，對它們執行相同的任務以找到精確的區域性最小值。
示例
#include<iostream>
using namespace std;
int localMinima(int arr[], int left, int right, int n) {
int mid = left + (right - left)/2;
if ((mid == 0 || arr[mid-1] > arr[mid]) && (mid == n-1 || arr[mid+1] > arr[mid]))
return mid;
else if (mid > 0 && arr[mid-1] < arr[mid])
return localMinima(arr, left, (mid -1), n);
return localMinima(arr, (mid + 1), right, n);
}
int findLocalMinima(int arr[], int n) {
return localMinima(arr, 0, n-1, n);
}
int main() {
int arr[] = {9, 6, 3, 14, 5, 7, 4};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Local minima is: " << arr[findLocalMinima(arr, n)];
}輸出
Local minima is: 3
更新於： 2019-12-18
374 次瀏覽
廣告