C++のローテーションリストで最大数を見つけるプログラム

配列があり、それがソートされていると仮定します。配列がピボットで回転していると考えてください。これは私たちにはわかりません。したがって、その回転した配列から最大値を見つける必要があります。したがって、配列が[3,4,5,1,2]のような場合、出力は5になります。

これを解決するには、次の手順に従います-

• low：=0およびhigh：=配列の最後のインデックス、n：=配列のサイズ、ans：=0

• 低<=高

  • 中：=低+（高-低）/ 2

  • arr [low]

  • それ以外の場合、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 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