Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++의 회전 정렬된 배열 II에서 최소값 찾기

<시간/>

정렬된 배열이 있고 이제 일부 피벗에서 회전한다고 가정합니다. 피벗은 이전에 알려지지 않았습니다. 해당 배열에서 최소 요소를 찾아야 합니다. 따라서 배열이 [4,5,5,5,6,8,2,3,4]와 같으면 최소 요소는 2입니다.

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

  • search()라는 하나의 메서드를 정의합니다. 이것은 arr, low 및 high를 취합니다.

  • 낮음 =높음이면 arr[낮음]

    을 반환합니다.

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

  • ans :=inf

  • if arr[low]

  • 그렇지 않으면 arr[high]> arr[mid]일 때 ans :=min of arr[mid] 및 search(arr, low, mid)

  • 그렇지 않으면 arr[low] =arr[mid]일 때 ans :=arr[low]의 min 및 search(arr, low + 1, high)

  • 그렇지 않으면 arr[high] =arr[mid]일 때 ans :=arr[high]의 min 및 search(arr, low, high - 1)

  • 반환

  • 기본 메소드 호출에서 solve(nums, 0, size of nums – 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 = INT_MAX;
      if(arr[low] < arr[mid]){
         ans = min(arr[low], search(arr, mid, high));
      }
      else if (arr[high] > arr[mid]){
         ans = min(arr[mid], search(arr, low, mid));
      }
      else if(arr[low] == arr[mid]){
         ans = min(arr[low], search(arr, low + 1, high));
      }
      else if(arr[high] == arr[mid]){
         ans = min(arr[high], search(arr, low, high - 1));
      }
      return ans;
   }
   int findMin(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.findMin(v));
}

입력

[4,5,5,5,6,8,2,3,4]

출력

2