程序在C ++中的轮换列表中查找最大数目

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

假设有一个数组，并且已排序，请考虑将数组旋转到某个枢轴，这对我们来说是未知的。因此，我们必须从该旋转数组中找到最大值。因此，如果数组像[3,4,5,1,2]，则输出将为5。

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

  • 低：= 0和高：=数组的最后一个索引，n：=数组的大小，ans：= 0

  • 而低<=高

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

    • 如果arr [low] <arr [mid]，则ans：= ans和arr [low]的最大值，low：=中+ 1

    • 否则，如果arr [high]> arr [mid]，则ans：= ans和arr [mid]的最大值，high：=中– 1

    • 否则，如果low = mid，则ans：= ans和arr [low]的最大值，low：= mid + 1

    • 否则，如果high =中，则ans：= ans和arr [high]的最大值，high：=中-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

以上是 程序在C ++中的轮换列表中查找最大数目 的全部内容， 来源链接： utcz.com/z/338300.html

回到顶部