在C ++中的旋转排序数组II中查找最小值

假设我们有一个已排序的数组,现在它已在某个轴上旋转了。枢轴以前未知。我们必须从该数组中找到最小的元素。因此,如果数组类似于[4,5,5,5,6,8,2,3,4],则最小元素为2。

为了解决这个问题,我们将遵循以下步骤-

  • 定义一个称为的方法search(),这需要arr,low和high

  • 如果低=高,则返回arr [低]

  • 中:=低+(高–低)/ 2

  • ans:= inf

  • 如果arr [low] <arr [mid],则ans:= min of arr [low] and search(arr,mid,high)

  • 否则,当arr [high]> arr [mid]时,则ans:= min of arr [mid]并搜索(arr,low,mid)

  • 否则,当arr [low] = arr [mid]时,则ans:= min of arr [low]并搜索(arr,低+ 1,高)

  • 否则,当arr [high] = arr [mid]时,则ans:= min of arr [high]并搜索(arr,low,high-1)

  • 返回ans

  • 从主方法调用solve(nums,0,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

以上是 在C ++中的旋转排序数组II中查找最小值 的全部内容, 来源链接: utcz.com/z/340943.html

回到顶部