当前位置: 首页 > 图灵资讯 > 技术篇> LeetCode面试题:寻找旋转排序数组中的最小值 II

LeetCode面试题:寻找旋转排序数组中的最小值 II

来源:图灵教育
时间:2023-05-16 09:18:41

  1.简述:

  已知的长度是 n 提前按升序排列的数组,通过 1 到 n 次 旋转 之后,输入数组。例如,原数组 nums = [0,1,4,4,5,6 可以在变化后得到:

  若旋转 4 第二,可以得到 [4,5,6,7,0,1,4]

  若旋转 7 第二,可以得到 [0,1,4,4,5,6

  注意,数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 结果是数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

  给你一个可能的存在 重复 元素值的数组 nums ,它最初是一个升序排列的数组,并根据上述情况多次旋转。请找出并返回数组 最小元素 。

  您必须尽可能减少整个过程的操作步骤。

  示例 1:

  输入:nums = [1,3,5]

  输出:1

  示例 2:

  输入:nums = [2,2,0,1]

  输出:0

  2.实现代码:class Solution { public int findMin(int[] nums) { int low = 0; int high = nums.length - 1; while (low < high) { int pivot = low + (high - low) / 2; if (nums[pivot] < nums[high]) { high = pivot; } else if (nums[pivot] > nums[high]) { low = pivot + 1; } else { high -= 1; } } return nums[low]; }}