精华内容
下载资源
问答
  • 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 方法 直接遍历,找到...

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

    方法
    • 直接遍历,找到最小值。

    • 从前往后找,同时从后往前找

    • 二分查找。

    import java.util.ArrayList;
    public class Solution {
        public int minNumberInRotateArray(int [] array) {
        
            if (array.length == 0) {
                return 0;
            } 
            
             if(array.length==1){
                return array[0];
            }
           
            for (int i = 0; i < array.length; i++) {
                if (array[i] > array[i + 1]) {
                    return array[i + 1];
                }
            }
            return 0;
          
        }
    }
    
    import java.util.ArrayList;
    public class Solution {
        public int minNumberInRotateArray(int [] array) {
        
            if (array.length == 0) {
                return 0;
            } 
            
             if(array.length==1){
                return array[0];
            }
           
            for (int i = 0; i < array.length; i++) {
                
                //从前往后找
                if (array[i] > array[i + 1]) {
                    return array[i + 1];
                }
                
                //从后往前找
                if (array[array.length - 1 - i] < array[array.length - 2 - i]) {
                    return array[array.length - 1 - i];
                }
            }
            return 0;
          
        }
    }
    
    import java.util.ArrayList;
    public class Solution {
        public int minNumberInRotateArray(int [] array) {
        
            if (array.length == 0) {
                return 0;
            } 
            
             if(array.length==1){
                return array[0];
            }
           
           int first = 0;
           int last = array.length - 1;
    
            while (first < last) {
               int mid =  first + (last - first)  / 2;
               //中间元素大于最后元素,最小值在右区间
               if (array[mid] > array[last]) {
                 first = mid + 1;
                   //中间元素小于最后元素,最小值在左区间
               } else if (array[mid] < array[last]) {
                   last = mid;
                    //相等无法确定区间,但是可以把后指针前移
               } else {
                    last--;
               }
            }
            return array[first];
              
        }
    }
    
    展开全文
  • 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 解题思路:采取栈存取...

    题目描述

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

    解题思路:采取栈存取最小值,当数组值小于栈,则push到栈中,最终栈的pop就是最小值

    剑指offer的代码:

    import java.util.ArrayList;
    import java.util.Stack;
    public class Solution {
        public int minNumberInRotateArray(int [] array) {
        Stack<Integer> stack = new Stack<Integer>();
             stack.push(array[0]);
                for(int i=0;i<array.length;i++){
                    if(array[i]<stack.peek())
                        stack.push(array[i]);
                }
                return stack.peek();
        }
    }

    1. 本机测试的代码:
    2. package pratice712;
    3. import java.util.ArrayList;
    4. import java.util.Stack;
    5. public class RotateMinnum712 {
    6.      public static int minNumberInRotateArray(int [] array) {
    7.          Stack<Integer> stack = new Stack<Integer>();
    8.          stack.push(array[0]);
    9.             for(int i=0;i<array.length;i++){
    10.                 if(array[i]<stack.peek())
    11.                     stack.push(array[i]);
    12.             }
    13.             return stack.peek();
    14.         }
    15.     public static void main(String[] args) {
    16.         int array[] = {3,4,5,1,2};
    17.         int min = minNumberInRotateArray(array);
    18.         System.out.print("min: "+min);
    19.     }
    20. }

    扫码关注一起随时随地学习!!!就在洋葱攻城狮,更多精彩,等你来!!

    展开全文
  • 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 又例如{1,0,1,1,1}和{1,1,1,0,1}都可以看成是递增排序数组{0,1,1,1,1}的...
  • 旋转数组的最小数字

    2021-03-15 13:32:58
    return rotateArray[length-1] 人生苦短,我用Python 发表于 2016-08-27 14:51:27 回复(30) 13 public class Solution { /* * 传进去旋转数组,注意旋转数组的特性: * 1.包含两个有序序列 * 2.最小数一定位于第二...

    532

    推荐

    思路

    剑指Offer中

    查看全部

    编辑于 2015-08-18 23:34:39

    回复(140)

    703

    采用二分法解答这个问题,

    mid = low + (high - low)/2

    需要考虑三种情况:

    (1)array[mid] > array[high]:

    出现这种情况的array类似[3,4,5,6,0,1,2],此时最小数字一定在mid的右边。

    low = mid + 1

    (2)array[mid] == array[high]:

    出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1],此时最小数字不好判断在mid左边

    还是右边,这时只好一个一个试 ,

    high = high - 1

    (3)array[mid] < array[high]:

    出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左

    边。因为右边必然都是递增的。

    high = mid

    注意这里有个坑:如果待查询的范围最后只剩两个数,那么mid 一定会指向下标靠前的数字

    比如 array = [4,6]

    array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ;

    如果high = mid - 1,就会产生错误, 因此high = mid

    但情形(1)中low = mid + 1就不会错误 public class Solution {

    public int minNumberInRotateArray(int [] array) {

    int low = 0 ; int high = array.length - 1;

    while(low < high){

    int mid = low + (high - low) / 2;

    if(array[mid] > array[high]){

    low = mid + 1;

    }else if(array[mid] == array[high]){

    high = high - 1;

    }else{

    high = mid;

    }

    }

    return array[low];

    }

    }

    编辑于 2017-08-01 13:06:40

    回复(202)

    46

    //C++ 二分法

    class Solution {

    public:

    int minNumberInRotateArray(vector rotateArray) {

    if (rotateArray.empty()) return 0;

    int left = 0, right = rotateArray.size() - 1;

    while (left < right) {

    //确认子数组是否是类似1,1,2,4,5,..,7的非递减数组

    if (rotateArray[left] < rotateArray[right]) return rotateArray[left];

    int mid = left + (right - left) / 2;

    //如果左半数组为有序数组

    if (rotateArray[left] < rotateArray[mid])

    left = mid + 1;

    //如果右半数组为有序数组

    else if (rotateArray[mid] < rotateArray[right])

    right = mid;

    //否则,rotateArray[left] == rotateArray[mid] == rotateArray[right]

    else {

    ++left;

    }

    }

    return rotateArray[left];

    }

    };

    发表于 2018-05-17 10:48:25

    回复(19)

    107

    三种方法,

    1、最笨的一种:

    遍历整个数组,找出其中最小的数。这样肯定拿不到offer

    2、稍微优化:

    public int minNumberInRotateArray(int[] array) {

    if (array.length == 0)

    return 0;

    for (int i = 0; i < array.length - 1; i++) {

    if (array[i] > array[i + 1])

    return array[i + 1];

    }

    return array[0];

    }

    3、二分查找:

    public static int minNumberInRotateArray(int[] array) {

    if (array.length == 0)

    return 0;

    int left = 0;

    int right = array.length - 1;

    int middle = -1;

    while (array[left]>=array[right]) {

    if(right-left==1){

    middle = right;

    break;

    }

    middle = left + (right - left) / 2;

    if (array[middle] >= array[left]) {

    left = middle;

    }

    if (array[middle] <= array[right]) {

    right = middle;

    }

    }

    return array[middle];

    }

    发表于 2017-01-09 10:57:17

    回复(46)

    46

    Python方法大总结

    方法一:直接min函数,有点像开挂

    class Solution:

    def minNumberInRotateArray(self, rotateArray):

    # write code here

    if not rotateArray:

    return 0

    else:

    return min(rotateArray)

    方法二:先sort排序

    class Solution:

    def minNumberInRotateArray(self, rotateArray):

    # write code here

    if not rotateArray:

    return 0

    else:

    rotateArray.sort()

    return rotateArray[0]

    方法三:二分查找

    class Solution:

    def minNumberInRotateArray(self, rotateArray):

    # write code here

    length = len(rotateArray)

    if length == 0:

    return 0

    elif length == 1:

    return rotateArray[0]

    else:

    left = 0

    right = length - 1

    while left < right:

    mid = (left + right)/2

    if rotateArray[mid] < rotateArray[j]:

    right = mid

    else:

    left = mid+1

    return rotateArray[i]

    方法四:比较

    class Solution:

    def minNumberInRotateArray(self, rotateArray):

    # write code here

    length = len(rotateArray)

    if length == 0:

    return 0

    elif length == 1:

    return rotateArray[0]

    else:

    for i in range(length-1):

    if rotateArray[i] > rotateArray[i+1]:

    return rotateArray[i+1]

    return rotateArray[length-1]

    人生苦短,我用Python

    发表于 2016-08-27 14:51:27

    回复(30)

    13

    public class Solution {

    /*

    * 传进去旋转数组,注意旋转数组的特性:

    * 1.包含两个有序序列

    * 2.最小数一定位于第二个序列的开头

    * 3.前序列的值都>=后序列的值

    * 定义把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。

    * ^_^这个旋转思想是很经典的

    * 旋转数组实例:

    * {123456}旋转后{456123}

    */

    //用到了快速排序的快速定位范围的思想,

    public int minNumberInRotateArray(int [] array) {

    if(array==null||array.length==0){ return 0;

    }

    int low=0;

    int up=array.length-1;

    int mid=low;

    // 当low和up两个指针相邻时候,就找到了最小值,也就是

    //右边序列的第一个值

    while(array[low]>=array[up]){

    if(up-low==1){

    mid=up;

    break;

    }

    //如果low、up、mid下标所指的值恰巧相等

    //如:{0,1,1,1,1}的旋转数组{1,1,1,0,1}

    if(array[low]==array[up]&&array[mid]==array[low])

    return MinInOrder(array);

    mid=(low+up)/2;

    //这种情况,array[mid]仍然在左边序列中

    if(array[mid]>=array[low])

    low=mid;//注意,不能写成low=mid+1;

    //要是这种情况,array[mid]仍然在右边序列中

    else if(array[mid]<=array[up])

    up=mid;

    }

    return array[mid];

    }

    private int MinInOrder(int[] array) {

    // TODO Auto-generated method stub

    int min =array[0];

    for(int i=1;i

    if(array[i]

    min=array[i];

    }

    }

    return min;

    }

    public static void main(String[] args) {

    }

    }

    编辑于 2015-04-11 17:55:45

    回复(5)

    80

    此题比较扯的。但题目还是不错。

    比较扯的原因:

    1.当数组为空的时候,测试用例需要返回0,我返回-1,结果没通过。

    2.明明题目说是递增数列,测试用里面竟然有非递减数列。

    正确做法需要分为:

    1.数组为空

    2.部分旋转,例如由(1,2,3,4,5)旋转为(3,4,5,1,2),此时只需要遍历数组,找到当前数比前面的数小的数即可。

    3.完全旋转,例如由(1,2,3,4,5)旋转为(1,2,3,4,5),此时第一个数最小。

    class Solution {

    public:

    int minNumberInRotateArray(vector rotateArray) {

    //数组为空时

    if(rotateArray.size() == 0)

    return -1;

    //前部分数据旋转

    for(int i = 0; i < rotateArray.size() - 1; i++){

    if (rotateArray[i] > rotateArray[i + 1])

    return rotateArray[i + 1];

    }

    //全部数据旋转,相当于没有旋转,最小数即为第一个数

    return rotateArray[0];

    }

    };

    发表于 2015-05-13 14:43:11

    回复(33)

    12

    /*把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。*/

    根据题意说明是一个递增数组的旋转,所以如题所示【3,4,5】,【1,2】还是局部递增的,在这种的数组中查找,一般选择二分的方法;基本模型有了,下面试着分析:

    1.先取出中间的数值,和最后一个比较5>2 说明mid之前的某些部分旋转到了后面,所以下次寻找 low = mid+1

    开始;

    2.取出的中间值要是小于high,说明mid-high之间都应为被旋转的部分,所以最小应该在mid的前面,但是也有可能当前的mid

    就是最小的值 所以下次需找的应该 从mid开始,也即high = mid 开始

    3.当*mid == *high的时候,说明数组中存在着相等的数值,可能是这样的形式

    【2,2,2,2,1,2】所以应该选择的high 应该递减1 作为下次寻找的上界。

    参考代码如下:

    int minNumberInRotateArray(vector rotateArray) {

    size_t len = rotateArray.size();

    if(len == 0)

    return 0;

    if(len == 1)

    return rotateArray[0];

    vector::iterator low = rotateArray.begin();

    vector::iterator mid;

    vector::iterator high = rotateArray.end()-1;

    while(low <= high)

    {

    //防止迭代器失效

    mid = low + (high - low)/2;

    if(*mid >*high)

    {

    low = mid + 1;

    }

    else if(*mid < *high)

    {

    high = mid;

    }

    else

    {

    high = high-1;

    }

    if(low >= high)

    {

    break;

    }

    }

    return *low;

    }

    发表于 2015-08-11 14:03:13

    回复(6)

    5

    JavaScript

    看了排行第一大佬 念润 的解法和其回复内泥点药丸 的补充,得到如下解法: function minNumberInRotateArray(rotateArray) {

    var left = 0,

    length = rotateArray.length,

    right = length - 1,

    mid;

    if (length == 0) { return 0; }

    while (rotateArray[left] >= rotateArray[right]) {

    if (rotateArray[left] == rotateArray[right]) {

    // 对left去重,使其指向最后一个重复的数字

    for (var i = left; i < right; i++) {

    if (rotateArray[left] != rotateArray[i]) {

    left =i-1;

    break;

    }

    }

    // 对right去重,使其指向最前一个重复的数字

    for (var i = right; i > left; i--) {

    if (rotateArray[right] != rotateArray[i]) {

    right = i+1;

    break;

    }

    }

    }

    if (right - left <= 1) {

    mid = right;

    break;

    }

    // 四舍五入取整数,否则得到的就是小数,会报错;

    mid = Math.round(left + (right - left) / 2);

    if (rotateArray[mid] >= rotateArray[left]) {

    left = mid;

    } else {

    right = mid;

    }

    }

    return rotateArray[mid];

    }

    编辑于 2019-05-07 19:52:50

    回复(1)

    4

    其实就是二分查找,查找时分两种情况:

    1、array[m] > array[r]:说明旋转后最小值在右区间

    2、array[m] < array[r]:说明旋转后最小值在左区间

    (l、r是待查找区间边界,m是区间中间位置)

    class Solution { public:

    int minNumberInRotateArray(vector array) {

    //二分查找

    if(array.size()==0){

    return 0;

    }

    int l=0, r=array.size()-1;

    while(l

    int m = (l+r)>>1;

    if(array[m] > array[r]){

    l = m+1;

    }else{

    r = m;

    }

    }

    return array[l];

    }

    };

    发表于 2018-02-01 20:27:37

    回复(5)

    16

    python solution: # -*- coding:utf-8 -*-

    class Solution:

    def minNumberInRotateArray(self, rotateArray):

    # write code here

    return min(rotateArray)

    发表于 2017-10-07 19:14:16

    回复(21)

    9

    前方大坑!!

    rotateArray.size() == 0时候返回一个0

    这个设定极其不合理,无法区分是min=0还是出错了

    递归代码:

    class Solution {

    int findMin(vector a, int first, int last) {

    if (first >= last) return a[last];

    int mid = (first + last) / 2;

    if (a[first] == a[last] && a[mid] == a[first]) {

    // linear search

    int min = a[first];

    for (int i = first + 1; i <= last; i++)

    min = a[i]

    return min;

    }

    if (a[first] < a[last]) {

    return a[first];

    } else {

    if (a[mid] >= a[first]) {

    return findMin(a, mid + 1, last);

    } else {

    return findMin(a, first, mid);

    }

    }

    }

    public:

    int minNumberInRotateArray(vector rotateArray) {

    int n = rotateArray.size();

    if (n == 0) return 0;

    return findMin(rotateArray, 0, n - 1);

    }

    };

    循环代码:

    class Solution {

    public:

    int minNumberInRotateArray(vector array) {

    if (array.size() == 0) return 0;

    int first = 0, last = array.size() - 1;

    int mid = (first + last) / 2;

    while (array[first] >= array[last]) {

    if (last - first == 1) return array[last];

    if (array[first] == array[mid] && array[mid] == array[last]) {

    // linear search

    int min = array[first];

    for (int i = first + 1; i <= last; i++)

    min = array[i]

    return min;

    }

    if (array[first] <= array[mid]) first = mid;

    else last = mid;

    mid = (first + last) / 2;

    }

    return array[first];

    }

    };

    编辑于 2015-07-27 14:12:26

    回复(7)

    7

    # -*- coding:utf-8 -*-

    class Solution:

    def minNumberInRotateArray(self, rotateArray):

    # write code here

    for i in range(len(rotateArray)):

    if rotateArray[i+1] < rotateArray[i]:

    return rotateArray[i+1]

    return 0

    发表于 2018-03-20 16:05:21

    回复(1)

    3

    package go.jacob.day0827.剑指offer系列;

    public class 旋转数组的最小数字 {

    public int minNumberInRotateArray(int[] array) {

    if (array == null || array.length == 0) {

    return -1;

    }

    int len = array.length;

    int index1 = 0;

    int index2 = len - 1;

    int indexMid = index1;

    while (array[index1] >= array[index2]) {

    if (index1 == index2 - 1) {

    indexMid = index2;

    break;

    }

    indexMid = index1 + (index2 - index1) / 2;

    if (array[index1] <= array[indexMid]) {

    index1 = indexMid;

    } else if (array[indexMid] <= array[index2]) {

    index2 = indexMid;

    }

    }

    return array[indexMid];

    }

    }

    编辑于 2018-09-04 13:48:00

    回复(1)

    5

    我这个代码感觉挺简单的,测试通过。求大家挑挑毛病

    class Solution {

    public:

    int minNumberInRotateArray(vector rotateArray) {

    if(rotateArray.size()==0){

    return 0;

    }

    int min = rotateArray[0];

    for(int i=1;i

    if(rotateArray[i]

    min = rotateArray[i];

    break;

    }

    }

    return min;

    }

    };

    发表于 2015-05-04 23:51:41

    回复(21)

    4

    # -*- coding:utf-8 -*-

    class Solution:

    def minNumberInRotateArray(self, rotateArray):

    # 可以使用min()函数, 但是在不适用min函数的情况下,思路应该是二分查找

    # 下面使用 递归实现2分查找,其中递归的时候必须使用return!!! 不然会返回none

    # write code here

    start = 0

    end = len(rotateArray) - 1

    mid = int((start + end) / 2)

    if len(rotateArray) == 2:

    if rotateArray[0]>rotateArray[1]:

    return rotateArray[1]

    else:

    return rotateArray[0]

    elif rotateArray[mid] > rotateArray[end]:

    return self.minNumberInRotateArray(rotateArray[mid:end + 1])

    elif rotateArray[mid] < rotateArray[start]:

    return self.minNumberInRotateArray(rotateArray[start:mid + 1])

    发表于 2018-04-17 21:38:33

    回复(4)

    4

    import java.util.ArrayList;

    public class Solution {

    public int minNumberInRotateArray(int [] array) {

    if(array.length == 0)

    return 0;

    int i = 0;

    while (i < array.length - 1 && array[i] <= array[++i])

    ;

    return i == array.length - 1 ? array[0] : array[i];

    }

    }

    我的思路是:首先数组长度为零时,返回零,因为测试要求这样。然后有一个特殊情况是没有旋转,那么返回array[0],其次一般情况while一直循环,知道后面的数 < 前面的数停止,这个数就是我们要找的。

    发表于 2015-08-18 09:52:20

    回复(7)

    4

    import java.util.ArrayList;

    public class Solution {

    public int minNumberInRotateArray(int [] array) {

    if (array != null && array.length >

    0) {

    int index1 = 0;

    int index2 = array.length - 1;

    int indexMid = index1;

    while (index1 <= index2) {

    indexMid = (index1 + index2) / 2;

    if (array[indexMid] == array[index2]

    && array[index1] == array[index2]) {

    int min = array[0];

    for (int i = 1; i < array.length; i++) {

    if (min > array[i]) {

    min = array[i];

    }

    }

    return min;

    }

    else if (array[indexMid] > array[index1]) {

    index1 = indexMid;

    } else {

    index2 = indexMid;

    }

    }

    return indexMid;

    } else {

    return 0;

    }

    }

    已经通过

    发表于 2015-08-15 17:46:48

    回复(1)

    2

    class Solution:

    def minNumberInRotateArray(self, rotateArray):

    # write code here

    return min(rotateArray)

    直接用min函数不就行了

    发表于 2020-03-06 21:17:47

    回复(2)

    2

    import java.util.ArrayList;

    public class Solution {

    public int minNumberInRotateArray(int [] array) {

    if(array.length==0)

    return 0;

    else

    return partition(array,0,array.length-1);

    }

    //递归的目的是寻找乱序的子数组

    private int partition(int [] array,int start,int end){

    if( array[start] < array[end] || start == end ) //如果第一个元素小于最后一个元素,说明数组从头到尾都是非减的;如果只剩下一个元素,则直接返回

    return array[start];

    else {

    int mid=start+(end-start)/2;

    if( array[mid] < array[end]){ //如果中间值下于最后的值,说明后半部分为非减序列,所以在前半部分继续寻找;

    //另外,之所以是mid而不是mid-1,是为了防止出现越界的情况,例如,array=[3,4],那么start=0,mid=0,end=1; (mid-1)等于-1,不可行

    return partition(array,start,mid);

    }else if(array[mid] == array[end]){ // 如果array=[1,0,1,1,1]或者[1,1,1,0,1],那没办法判断乱序子数组的位置,所以只能削减一步

    return partition(array,start,end-1);

    }else{ //如果中间值大于最后值,那么说明乱序的部分在后半段,所以在后半段寻找。可以使用mid+1是因为,中间值都比最后值大了,那还要它干嘛?

    return partition(array,mid+1,end);

    }

    }

    }

    }

    编辑于 2018-08-06 23:10:21

    回复(1)

    2

    C++实现,折半查找法

    class Solution {

    public:

    int minNumberInRotateArray(vector rotateArray) {

    int length = rotateArray.size();

    if(length == 0)

    return 0;

    int pre = 0;

    int last = length - 1;

    while(pre < last)

    {

    int mid = (pre + last) / 2;

    if(rotateArray[mid] > rotateArray[last])

    {

    pre = mid + 1;

    }

    else if(rotateArray[mid] < rotateArray[last]){

    last = mid;

    }

    else{

    last = last - 1;

    }

    }

    return rotateArray[pre];

    }

    };

    发表于 2018-03-14 21:11:18

    回复(1)

    展开全文
  • 旋转数组最小值

    2021-03-15 13:31:22
    输入一个排好序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。思路这道题最直观的解法并不难。从头到尾遍历数组一次,就能找出最小的元素,...

    问题

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个排好序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。

    思路

    这道题最直观的解法并不难。从头到尾遍历数组一次,就能找出最小的元素,时间复杂度显然是O(n)。但这个思路没有利用输入数组的特性。既然有时间复杂度更小的算法,我们容易想到二分查找,因为它的时间复杂度为O(logn)。这个问题是否可以运用二分查找呢?答案是肯定的。观察一下数组的特性,首先递增(称为递增a),然后突然下降到最小值,然后再递增(称为递增b)。当然还有一种特殊情况,就是数组递增,中间没有下降,即旋转元素个数为0。

    一般解法:找到中间下标,如果数组开始值小于中间下标对应的值,则表示中间下标属于第一个第一个递增,另开始下标等于中间下标,相反,如果中间下标对应的值小于结尾值,则表明,中间下标输入第二个递增,另结尾下标等于中间下标。直到开始下标和结尾下标相邻。

    特殊情况:旋转个数为0,例如{1,2,3,4,5},则可以通过第一个值小于最后一个值判断,直接输出第一个值。

    packageoffer008;importjava.util.Scanner;/*** @Title: Main.java

    * @Package: offer008

    * @Description 旋转数组的最小数字

    *@authorHan

    * @date 2016-4-18 上午10:39:35

    *@versionV1.0*/

    public classMain {public static voidmain(String[] args) {

    Scanner scanner= newScanner(System.in);int[] arr = null;int count = 0;while(scanner.hasNext()){//输入数组的大小

    count =scanner.nextInt();

    arr= new int[count];//输入数组

    for(int i = 0; i < count; i++){

    arr[i]=scanner.nextInt();

    }

    System.out.println(min(arr));

    }

    }/*** @Description 得到旋转数组中的最小值

    *@authorHan

    *@paramarr

    *@returnmin*/

    private static int min(int[] arr){//判断数组是否为空,长度是否为0

    if(arr == null || arr.length == 0){throw new RuntimeException("Error Input");

    }//头下标

    int startIndex = 0;//尾下标

    int endIndex = arr.length - 1;//中间下标

    int middleIndex = 0;//如果数组中的第一个值小于了最后一个值,则表明该数组为一个递增数组,直接输出第一个元素即可

    while(arr[startIndex] >=arr[endIndex]){//若该startIndex和endIndex相邻成立则表示endIndex指向的数字为最小值

    if(endIndex - startIndex == 1){

    startIndex=endIndex;break;

    }

    middleIndex= (startIndex + endIndex) / 2;//如果三个值相等,类似于1 0 1 1 1 1,则需要需要通过顺序查找出最小值

    if(arr[middleIndex] == arr[startIndex] && arr[middleIndex] ==arr[endIndex]){returnminByOrder(arr, startIndex, endIndex);

    }//若中间值大于startIndex指向的值,则移动startIndex到中间值

    if(arr[middleIndex] >=arr[startIndex]){

    startIndex=middleIndex;

    }else if(arr[middleIndex] <=arr[endIndex]){

    endIndex=middleIndex;

    }

    }returnarr[startIndex];

    }/*** @Description 顺序查找出最小值

    *@authorHan

    *@paramarr

    *@paramstartIndex

    *@paramendIndex

    *@return

    */

    private static int minByOrder(int[] arr, int startIndex, intendIndex) {int min =arr[startIndex];for(int i = startIndex + 1; i <= endIndex; i++){if(arr[i]

    min=arr[i];

    }

    }returnmin;

    }

    }

    结果

    a8a36abcdb8d29bd7ee29f09ef7cd395.png

    展开全文
  • 问题:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转,输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素,例如数组{3,4,5,1,2}为数组{1,2,3,4,5}的一个旋转,该数组的最小值为1。...
  • 解决: ① 本题与I的区别在于翻转数组中可能会存在重复。我们只需要添加一个条件,它检查最左边的元素和最右边的元素是否相等。 如果是的话,我们可以简单地放下其中一个。使用递归方法进行处理。 class Solution{ ...
  • 输入一个递增排序的数组的一个旋转输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。思路:1.直接遍历一次数组,...
  • 二分法变形,旋转数组的组成特点是,前面递增(不是严格的递增),后面递增(不是严格递增),但是前面部分大于等于后面部分。因此最小值就是两个部分的分界点。查询时,从中间开始查询,将中间值与前部分的最小值,...
  • 【编程题】旋转数组最小值Java实现) 题目来源 剑指offer第六题 https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=11159&rp=1&ru=/ta/coding-interviews&qru=...
  • 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 一、遍历数组 因为原...
  • 旋转数组最小值

    2018-04-04 12:10:36
    输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 //二分法查找定要...
  • 要求获取一个旋转数组最小值。这本质上是一个求最值的问题,最简单的方法就是顺序遍历数组,从中找出最小值,该方法的时间复杂度为O(n)。但这种方法会被面试官鄙视的,所以我们寻找更为...
  • /*** 找到旋转数组最小值* 由于部分有序,借用二分查找思想.三个游标index1,index2,indexMid* @author yanjie**/public class MinReverse {static int[] data = {5,6,7,8,9,1,2,3,4};//static int[] data = {1,0,1...
  • 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 import java.util....
  • 旋转数组中的最小数字 NowCoder 题目描述: 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的...
  • 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 一、Python: 1.1 直接...
  • 旋转数组中的最小数字 java 题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个...
  • 06 旋转数组最小值

    2019-11-02 09:24:29
    输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 第一遍读题没想明白…...
  • 微软面试题:寻找旋转排序数组中的最小值假设一个排好序的数组在其某一未知点发生了旋转(比如 0 1 2 4 5 6 7 可能变成 4 5 6 7 0 1 2 )。你需要找到其中最小的元素。样例 1:输入:[4, 5, 6, 7, 0, 1, 2]输出:0解释...
  • 需求:  假设一个旋转排序的数组其起始位置是未知的(比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2...如果是排序数组旋转,那么旋转之后的数组有可能是排序的,也有可能包含两个有序子数组,左边的有序数组中元素都
  • 输入一个递增排序数组的一个旋转,输出旋转数组最小值。 示例: 数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转 该数组的最小值为1。 答案: 一般情况 {3,4,5,1,2},二分查找 特殊情况一 : {1,1,1,0,1}或{1,0,1,1...
  • 中:旋转数组最小值

    2020-08-12 16:14:40
    输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 解: 我们把旋转数组...
  • 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。 你可以假设数组中不存在重复元素。 示例 1: ...
  • 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。 请找出其中最小的元素。 你可以假设数组中不存在重复元素。 示例 1: 输入: [3,4,5,1,2] ...
  • 寻找旋转排序数组中的最小值 -- leetcode 153 题目描述 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。 你可以...
  • 第153题:旋转排序数组最小值Ⅰ 假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。请找出其中最小的元素。你可以假设数组中不存在重复元素。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,529
精华内容 2,211
关键字:

旋转数组最小值java

java 订阅