博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
剑指Offer 11.旋转数组的最小数字
阅读量:317 次
发布时间:2019-03-03

本文共 1400 字,大约阅读时间需要 4 分钟。

剑指Offer 11.旋转数组的最小数字

在这里插入图片描述

简单法:
遍历数组,找到第一个左边的数大于右边,就返回右边的数,时间复杂度O(n)。

class Solution {    public int minArray(int[] numbers) {       for(int i = 0; i < numbers.length-1; i++)       {           if(numbers[i] > numbers[i+1])  return numbers[i+1];       }       return numbers[0];    }}

二分法:

时间复杂度O(logn),最差的时候为O(n)
声明 i, j 双指针分别指向 numbers 数组左右两端;m为i,j中点,当i<j时,判断
numbers[m]和numbers[j]的大小。分三种情况:
if(numbers[m] < numbers[j]) //说明m在右排序数组中,旋转点在左边
j = m;
else if(numbers[m] > numbers[j]) //说明m在左排序数组中,旋转点在右边
i = m + 1; //旋转点一定会在右排序数组中,所以i=m+1,免得多比较一个数
else if(numbers[m] == numbers[j]) //无法判断m在哪个数组中
j = j - 1;
第三种情况可能会错过旋转点,但是还是能返回与旋转点值相同的点
代码:

class Solution {    public int minArray(int[] numbers) {      int i,j,m;      i = 0;      j = numbers.length-1;      m = (i + j) / 2;      while(i < j) {         if(numbers[m] < numbers[j]) //说明m在右排序数组中,旋转点在左边         j = m;        else if(numbers[m] > numbers[j]) //说明m在左排序数组中,旋转点在右边         i = m + 1;        else if(numbers[m] == numbers[j]) //无法判断m在哪个数组中          j = j - 1;           m = (i + j) / 2;      }      return numbers[i];    }}

在这里插入图片描述


二刷

之前没有深刻理解当nums[j] == nums[mid]时,为什么j–一定是正确的。二刷时甚至忘记了当nums[j] == nums[mid]时,无法判断旋转点在哪一边。比如:3,3,3,3,3,4,5,3,3这个数组,第一次nums[mid] = 3,nums[j] = 3, 此时无法判断旋转点位置,j–,nums[mid] = 3,j会一直减到i的位置停下,返回nums[i],此时nums[i]虽然不是旋转点,但是与旋转点的值一定相同,因为左右都是递增序列。

这里总结一下:

1、左闭右闭区间,i = m + 1,j = m - 1,当i>j的时候停止.
2、左闭右开区间,i = m + 1, j = m,当i = j 的时候停止

转载地址:http://grim.baihongyu.com/

你可能感兴趣的文章