美文网首页
面试题11:旋转数组

面试题11:旋转数组

作者: 修司敦 | 来源:发表于2018-11-13 15:48 被阅读0次

把一个数组最开始的若干个元素搬到数组的末尾,成为数组的旋转。输入一个递增排序的数组的一个旋转,输出数组的最小元素。


解析:这题最容易想到的就是顺序搜索一遍,但是这样子的时间复杂度在 O(n)。我们可以用类似二分的思想来找到那个最小的元素,但是有一种特殊情况会让我们必须使用顺序查找,因为在这个特殊情况下无法判断是要往左半部分查找还是右半部分查找。

先想一下如何使用二分查找。我们把被旋转到末尾的那个小的递增片段计作 a,由于旋转作用而向前挪动了的剩下的那个递增片段计作 b。例如,原有片段是 {1,2,3,4,5,6,7,8},我把 {1,2,3} 旋转到后面,那么旋转后就变成了 {4,5,6,7,8,1,2,3}。这个时候,a={1,2,3},b={4,5,6,7,8}。我们在二分查找的时候,中间位置上的数字有可能落在 a 里,也有可能落在 b 里。如果落在 a 里面,那么最小的数字应该还在中间数字的左边。如果落在 b 里,最小的数字应该在中间数字的右边。用这个思想我们就可以不断的去逼近最小的数字。多写几个例子,模拟一边过程,你就会发现最后中间的数字指向的就是最小的数字。

我们考虑几种特殊情况。首先,当前比较的数组已经递增了。那么这个时候数组的第一位就是最小的数字,我们可以直接返回。我们可以把中间位的初始值设定为第一位,在每次进入循环的时候检查该数组是否已经递增。如果已经递增,就不需要进入循环了,直接返回第一位就好。然后是我刚说到的,无法使用二分查找的方法。考虑 {0,1,1,1,1},旋转前四位得到 {1,0,1,1,1}。开头、中间和结尾的位置都是1,那这个时候就无法判断要往左边走还是往右边走了。如果遇到了这个情况,那么只能顺序搜索当前序列,找到最小的元素。


答案:

int MinInOrder(int* numbers, int index1, int index2)
{
    int result = numbers[index1];
    for(int i = index1 + 1; i <= index2; ++i)
    {
        if(result > numbers[i])
            result = numbers[i];
    }

    return result;
}

int Min(int* numbers, int length)
{
    if(numbers == nullptr || length <= 0)
        throw exception();

    int first = 0, last = length-1;
    int mid = first; //将中间位初始为第一位
    while (numbers[first]>=numbers[last]) //如果该序列本身就是递增序列,退出 while
    {
        if (last-first == 1)
        {
            mid = last;
            break;
        }
        else
        {
            mid = first + ((last-first)>>1);
            if (numbers[first]==numbers[mid] && numbers[mid]==numbers[last])
                return MinInOrder(numbers, first, last);
            else
            {
                if (numbers[mid]>=numbers[first])
                    first = mid;
                else if (numbers[mid]<=numbers[first])
                    last = mid;
            }
        }
    }
    return numbers[mid];
}

相关文章

  • 旋转数组的最小数字

    《剑指offer》面试题11:旋转数组的最小数字 题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组...

  • 剑指offer第二版-11.旋转数组的最小数字(二分查找)

    本系列导航:剑指offer(第二版)java实现导航帖 面试题11:旋转数组的最小数字 题目要求:把一个数组最开始...

  • 面试题11:旋转数组

    把一个数组最开始的若干个元素搬到数组的末尾,成为数组的旋转。输入一个递增排序的数组的一个旋转,输出数组的最小元素。...

  • 11:旋转数组的最小数字

    题目11:旋转数组的最小数字 把一个数组最开始的若干个元素搬到数组的末尾, 我们称之数组的旋转。输入一个递增排序的...

  • 剑指offer面试题分类总结

    数组: 面试题3:数组中重复的数字面试题4:二维数组中的查找面试题21:调整数组顺序使奇数位于偶数前面面试题39:...

  • [剑指offer]08-旋转数组的最小数字

    旋转数组的最小数字 题目 给定一个递增的旋转数组A,返回旋转数组中的最小值。旋转数组:给定一个已排序的数组,假设为...

  • 旋转数组的最小值

    旋转数组的最小值 所谓旋转数组,即是递增有序数组旋转右移动若干位得到的数组,这里的右移和java里的>>>有点不同...

  • Day6 剑指offer:旋转数字的最小数

    把一个数组最开始的若干个数组搬到数组的末尾,我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转,输出旋转数组...

  • 39. 恢复旋转排序数组

    给定一个旋转排序数组,在原地恢复其排序。说明:什么是旋转数组?比如,原始数组为[1,2,3,4], 则其旋转数组可...

  • 面试题11-旋转数组求最小数

    题目要求 旋转数组是指将数组的元素逐个移动至数组尾部。现在有一个递增的数组,将数组旋转后,求数组的最小值。 题目解...

网友评论

      本文标题:面试题11:旋转数组

      本文链接:https://www.haomeiwen.com/subject/lxicfqtx.html