吉林平台网站建设推荐,个人网站建设论文,济南代做标书网站标志,wordpress代码缓存题目
把一个数组最开始的若干个元素搬到数组的末尾#xff0c;我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers #xff0c;它原来是一个升序排列的数组#xff0c;并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如#xff0c;数组 [3,4…题目
把一个数组最开始的若干个元素搬到数组的末尾我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers 它原来是一个升序排列的数组并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转该数组的最小值为 1。
注意数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。 示例 1 输入numbers [3,4,5,1,2]输出1 示例 2 输入numbers [2,2,2,0,1]输出0 提示
n numbers.length1 n 5000-5000 numbers[i] 5000numbers 原来是一个升序排序的数组并进行了 1 至 n 次旋转 解题思路 1.题目要求我们返回旋转数组的最小元素我们可以使用二分查找找到旋转排序数组中的最小元素。 2.首先初始化两个指针left和right它们分别表示数组的起始和结束索引。在while循环内部它检查left索引处的元素是否小于right索引处的元素。如果是则意味着数组已经按升序排序最小元素位于left索引处。因此它返回left索引处的元素。如果数组未排序则计算mid索引为left和right的平均值。 3.然后它将mid索引处的元素与left索引处的元素进行比较。如果mid索引处的元素大于left索引处的元素则意味着最小元素位于数组的右半部分。因此它将left指针更新为mid 1。如果mid索引处的元素小于left索引处的元素则意味着最小元素位于数组的左半部分。因此它将right指针更新为mid。如果mid索引处的元素等于left索引处的元素则意味着数组中存在重复元素。在这种情况下它将left指针增加1。 4.循环继续直到left指针小于right指针为止。此时left指针将指向数组中的最小元素并返回left索引处的元素。如果循环退出时仍未找到最小元素则意味着数组已经按升序排序最小元素位于left索引处。因此它返回left索引处的元素。 代码实现
class Solution {public int minArray(int[] numbers) {int left 0;int right numbers.length - 1;while(left right){if(numbers[left] numbers[right]){return numbers[left];}int mid (left right) / 2;if(numbers[mid] numbers[left]){left mid 1;}else if(numbers[mid] numbers[left]){right mid;}else{left ;}}return numbers[left];}}
测试结果
