โปรแกรมค้นหาจำนวนสูงสุดในรายการหมุนใน C++

สมมติว่ามีอาร์เรย์และมีการจัดเรียง ให้พิจารณาว่าอาร์เรย์ถูกหมุนที่จุดหมุนบางจุด ซึ่งเราไม่รู้จัก ดังนั้นเราจึงต้องหาค่าสูงสุดจากอาร์เรย์ที่หมุนนั้น ดังนั้นหากอาร์เรย์เป็นเหมือน[3,4,5,1,2] ผลลัพธ์จะเป็น 5

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ต่ำ :=0 และสูง :=ดัชนีสุดท้ายของอาร์เรย์ n :=ขนาดของอาร์เรย์ ans :=0

• ในขณะที่ต่ำ <=สูง

  • กลาง :=ต่ำ + (สูง - ต่ำ)/2

  • ถ้า arr[low]

  • else if arr[high]> arr[mid] แล้ว ans :=maximum of ans and arr[mid], high :=mid – 1

  • อื่นถ้าต่ำ =กลาง แล้ว ans :=สูงสุดของ ans และ arr[low], ต่ำ :=กลาง + 1

  • else if high =mid แล้ว ans :=maximum of ans and arr[high], high :=mid - 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 = 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