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

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个已排序的数组，现在它已在某个轴上旋转了。枢轴以前未知。我们必须从该数组中找到最小的元素。因此，如果数组类似于[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

回到顶部