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

题目描述

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

一 . 方法分析（正常单调递增数组）

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

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

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

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

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

可参考下例：

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

2. 把P_mid定义为P1，新的P_mid为1，这时候P_mid<P1且P_mid<P2，说明P_mid到 P2是单增，把新的P_mid定义为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 <= )

        {

            return ;

        }

        //定义三个参数，用于后期的指针

        int a = ;

        int b = rotateArray.Length - ;

        int mid = ;

        //while终止条件（每次前者大于后者的时候均要对比，当二者差一个数据位时终止返回）

        while(rotateArray[a]>=rotateArray[b])

        {

            if(b - a == )

            {

                mid = b;

                break;

            }

        //二分查找法，对mid参数的修改

        mid = (b+a)/;

        //特殊情况，特殊对待（即数列中存在相等参数时，就采用顺序查找法）

        if(rotateArray[a] == rotateArray[mid] && rotateArray[mid] == rotateArray[b])

        {

            int min = rotateArray[a];

            for(int i = ;i<rotateArray.Length-;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];

    }

}

巴特西

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

题目描述

一 . 方法分析（正常单调递增数组）

二 . 特殊条件

三 . 代码实现

最新文章

热门文章