C++의 회전 목록에서 최대 수를 찾는 프로그램

배열이 있고 정렬되어 있다고 가정하고 배열이 우리에게 알려지지 않은 일부 피벗에서 회전한다고 가정합니다. 따라서 회전된 배열에서 최대값을 찾아야 합니다. 따라서 배열이 [3,4,5,1,2]와 같으면 출력은 5가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• low :=0 and high :=배열의 마지막 인덱스, n :=배열의 크기, ans :=0

• 낮음 <=높음

  동안

  • 중간 :=낮음 + (높음 - 낮음)/2

  • arr[low]

  • else if arr[high]> arr[mid], 그러면 ans :=ans의 최대값이고 arr[mid], high :=mid – 1

  • else if low =mid이면 ans :=ans의 최대값이고 arr[low], low :=mid + 1

  • else if high =mid, ans :=ans 및 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