剑指Offer的学习笔记(C#篇)-- 旋转数组的最小数字

题目描述

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

一 . 方法分析(正常单调递增数组)

        1 . 参考二分查找法,我们用两个指针分别指向数组的第一个元素和最后一个元素。

  2 . 基于二分查找法的概念,找到数组中间的元素:因为该题目是查找旋转数组中的最小值。

            如果该中间元素位于前面的递增子数组,那么它应该大于或者等于第一个指针指向的元素。此时数组中最小的元素应该位于该中间元素的后面。我们可以把第一个指针指向该中间元素,这样可以缩小寻找的范围。移动之后的第一个指针仍然位于前面的递增子数组之中。

            如果中间元素位于后面的递增子数组,那么它应该小于或者等于第二个指针指向的元素。此时该数组中最小的元素应该位于该中间元素的前面。

  3 . 接下来我们再用更新之后的两个指针,重复做新一轮的查找。

可参考下例:

        1. 确定Pmid为5,Pmid>P1且Pmid>P2,说明P1到Pmid为单增。

        2. 把Pmid定义为P1,新的Pmid为1,这时候Pmid<P1且Pmid<P2,说明Pmid到 P2是单增,把新的Pmid定义为P2。

        3. 这时候P1>P2,且位置相差为1,结束,得出最小数为P2。

二 . 特殊条件

        1 . 鲁棒判断:即数组长度为0或者为空数组时,应返回0.

        2 . 存在相等的数。

        例:

         1. 有重复数字,并且重复的数字刚好的最小的数字。    { 3, 4, 5, 1, 1, 2 }

         2. 有重复数字,但重复的数字不是第一个数字和最后一个数字。   { 3, 4, 5, 1, 2, 2 }

         3. 单调升序数组,旋转0个元素,也就是单调升序数组本身。{ 1, 0, 1, 1, 1 }

         4. 数组中只有一个数字。{ 1 }

        适当的采用顺序查找法。太晚了,明天写吧!!

三 . 代码实现

class Solution
{
    public int minNumberInRotateArray(int[] rotateArray)
    {
        // write code here
        //鲁棒判断
        if(rotateArray == null || rotateArray.Length <= 0)
        {
            return 0;
        }
        //定义三个参数,用于后期的指针
        int a = 0;
        int b = rotateArray.Length - 1;
        int mid = 0;
        //while终止条件(每次前者大于后者的时候均要对比,当二者差一个数据位时终止返回)
        while(rotateArray[a]>=rotateArray[b])
        {
            if(b - a == 1)
            {
                mid = b;
                break;
            }
        //二分查找法,对mid参数的修改
        mid = (b+a)/2;
        //特殊情况,特殊对待(即数列中存在相等参数时,就采用顺序查找法)
        if(rotateArray[a] == rotateArray[mid] && rotateArray[mid] == rotateArray[b])
        {
            int min = rotateArray[a];
            for(int i = 0;i<rotateArray.Length-1;i++)
            {
                if(min<rotateArray[i])
                {
                    min = rotateArray[i];
                }
            }
        }
        //二分查找法,前后指针的修改
        if(rotateArray[mid]>=rotateArray[a])
        {
            a = mid;
        }
        if(rotateArray[mid]<=rotateArray[b])
        {
            b = mid;
        }
        }
        //返回最小值
        return rotateArray[mid];
    }
}

 

全部评论

相关推荐

06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
完美的潜伏者许愿简历...:隐藏信息被你提取出来了,暗示,这就是暗示
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务