那个网站专门做二手衣服的,成都哪家公司做网站比较好,wordpress 免费注册,零基础建设网站视频❓剑指 Offer 11. 旋转数组的最小数字
难度#xff1a;简单
把一个数组最开始的若干个元素搬到数组的末尾#xff0c;我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers #xff0c;它原来是一个升序排列的数组#xff0c;并按上述情形进行了一次旋转…❓剑指 Offer 11. 旋转数组的最小数字
难度简单
把一个数组最开始的若干个元素搬到数组的末尾我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 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 次旋转
注意本题与 154. 寻找旋转排序数组中的最小值 II 相同。
思路二分查找
将旋转数组对半分可以得到一个包含最小元素的新旋转数组以及一个非递减排序的数组。新的旋转数组的长度是原数组的一半从而将问题规模减少了一半这种折半性质的算法的时间复杂度为 O ( l o g 2 N ) O(log2N) O(log2N)。 此时问题的关键在于确定对半分得到的两个数组哪一个是旋转数组哪一个是非递减数组。我们很容易知道非递减数组的第一个元素一定小于等于最后一个元素。
通过修改二分查找算法进行求解left、mid、right 分别代表包含最小元素的新旋转数组 左、中、右
当 numbers[mid] numbers[right]时 [leftmid] 区间内的数组是非递减数组[mid 1, right] 区间内的数组为新的旋转数组此时left mid 1当 numbers[mid] numbers[right]时 [midright] 区间内的数组是非递减数组[left, mid] 区间内的数组为新的旋转数组此时right mid当 numbers[mid] numbers[right]时 无法判断哪一个是旋转数组哪一个是非递减数组此时 right- -直到能判断。
代码(C、Java)
C
class Solution {
public:int minArray(vectorint numbers) {int left 0;int right numbers.size() - 1;if(right 0) return numbers[0];while(left right){int mid left (right - left) / 2;if(numbers[mid] numbers[right]){left mid 1;}else if(numbers[mid] numbers[right]){right mid;}else{right--;}}return numbers[left];}
};Java
class Solution {public int minArray(int[] numbers) {int left 0;int right numbers.length - 1;if(right 0) return numbers[0];while(left right){int mid left (right - left) / 2;if(numbers[mid] numbers[right]){left mid 1;}else if(numbers[mid] numbers[right]){right mid;}else{right--;}}return numbers[left];}
}运行结果 复杂度分析
时间复杂度 O ( l o g n ) O(logn) O(logn)平均时间复杂度为 O ( l o g n ) O(logn) O(logn)其中 n 是数组 numbers 的长度。如果数组是随机生成的那么数组中包含相同元素的概率很低在二分查找的过程中大部分情况都会忽略一半的区间。而在最坏情况下如果数组中的元素完全相同那么 while 循环就需要执行 n 次每次忽略区间的右端点时间复杂度为 O(n)。空间复杂度 O ( 1 ) O(1) O(1)。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我LeetCode主页 / CSDN—力扣专栏每日更新 注 如有不足欢迎指正
