面试题:Java 实现查找旋转数组的最小数字
在算法面试中,面试官总是喜欢围绕链表、排序、二叉树、二分查找来做文章,而大多数人都可以跟着专业的书籍来做到倒背如流。而面试官并不希望招收的是一位记忆功底很好,但不会活学活用的程序员。所以学会数学建模和分析问题,并用合理的算法或数据结构来解决问题相当重要。
面试题:打印出旋转数组的最小数字
题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为数组{1,2,3,4,5}的一个旋转,该数组的最小值为1。
要想实现这个需求很简单,我们只需要遍历一遍数组,找到最小的值后直接退出循环。代码实现如下:
publicclassTest08{ publicstaticintgetTheMin(intnums[]){ if(nums==null||nums.length==0){ thrownewRuntimeException("inputerror!"); } intresult=nums[0]; for(inti=0;i打印结果没什么毛病。不过这样的方法显然不是最优的,我们看看有没有办法找出更加优质的方法处理。
有序,还要查找?
找到这两个关键字,我们不免会想到我们的二分查找法,但不少小伙伴肯定会问,我们这个数组旋转后已经不是一个真正的有序数组了,不过倒像是两个递增的数组组合而成的,我们可以这样思考。
我们可以设定两个下标low和high,并设定mid=(low+high)/2,我们自然就可以找到数组中间的元素array[mid],如果中间的元素位于前面的递增数组,那么它应该大于或者等于low下标对应的元素,此时数组中最小的元素应该位于该元素的后面,我们可以把low下标指向该中间元素,这样可以缩小查找的范围。
同样,如果中间元素位于后面的递增子数组,那么它应该小于或者等于high下标对应的元素。此时该数组中最小的元素应该位于该中间元素的前面。我们就可以把high下标更新到中位数的下标,这样也可以缩小查找的范围,移动之后的high下标对应的元素仍然在后面的递增子数组中。
不管是更新low还是high,我们的查找范围都会缩小为原来的一半,接下来我们再用更新的下标去重复新一轮的查找。直到最后两个下标相邻,也就是我们的循环结束条件。
说了一堆,似乎已经绕的云里雾里了,我们不妨就拿题干中的这个输入来模拟验证一下我们的算法。
- input:{3,4,5,1,2}
- 此时low=0,high=4,mid=2,对应的值分别是:num[low]=3,num[high]=2,num[mid]=5
- 由于num[mid]>num[low],所以num[mid]应该是在左边的递增子数组中。
- 更新low=mid=2,num[low]=5,mid=(low+high)/2=3,num[mid]=1;
- high-low≠1,继续更新
- 由于num[mid]
- 更新high=mid=3,由于high-mid=1,所以结束循环,得到最小值num[high]=1;
我们再来看看Java中如何用代码实现这个思路:
publicclassTest08{ publicstaticintgetTheMin(intnums[]){ if(nums==null||nums.length==0){ thrownewRuntimeException("inputerror!"); } //如果只有一个元素,直接返回 if(nums.length==1) returnnums[0]; intresult=nums[0]; intlow=0,high=nums.length-1; intmid; //确保low下标对应的值在左边的递增子数组,high对应的值在右边递增子数组 while(nums[low]>=nums[high]){ //确保循环结束条件 if(high-low==1){ returnnums[high]; } //取中间位置 mid=(low+high)/2; //代表中间元素在左边递增子数组 if(nums[mid]>=nums[low]){ low=mid; }else{ high=mid; } } returnresult; } publicstaticvoidmain(String[]args){ //典型输入,单调升序的数组的一个旋转 int[]array1={3,4,5,1,2}; System.out.println(getTheMin(array1)); //有重复数字,并且重复的数字刚好的最小的数字 int[]array2={3,4,5,1,1,2}; System.out.println(getTheMin(array2)); //有重复数字,但重复的数字不是第一个数字和最后一个数字 int[]array3={3,4,5,1,2,2}; System.out.println(getTheMin(array3)); //有重复的数字,并且重复的数字刚好是第一个数字和最后一个数字 int[]array4={1,0,1,1,1}; System.out.println(getTheMin(array4)); //单调升序数组,旋转0个元素,也就是单调升序数组本身 int[]array5={1,2,3,4,5}; System.out.println(getTheMin(array5)); //数组中只有一个数字 int[]array6={2}; System.out.println(getTheMin(array6)); //数组中数字都相同 int[]array7={1,1,1,1,1,1,1}; System.out.println(getTheMin(array7)); //特殊的不知道如何移动 int[]array8={1,0,1,1,1}; System.out.println(getTheMin(array8)); } }前面我们提到在旋转数组中,由于是把递增排序数组的前面的若干个数字搬到数组后面,因为第一个数字总是大于或者等于最后一个数字,而还有一种特殊情况是移动了0个元素,即数组本身,也是它自己的旋转数组。这种情况本身数组就是有序的了,所以我们只需要返回第一个元素就好了,这也是为什么我先给result赋值为nums[0]的原因。
上述代码就完美了吗?我们通过测试用例并没有达到我们的要求,我们具体看看array8这个输入。先模拟计算机运行分析一下:
- low=0,high=4,mid=2,nums[low]=1,nums[high]=1,nums[mid]=1;
- 由于nums[mid]>=nums[low],故认定nums[mid]=1在左边递增子数组中;
- 所以更新high=mid=2,mid=(low+high)/2=1;
- nums[low]=1,nums[mid]=1,nums[high]=1;
- high-low≠1,继续循环;
- 由于nums[mid]>=nums[low],故认定nums[mid]=1在左边递增子数组中;
- 所以更新high=mid=1,由于high-low=1,故退出循环,得到result=1;
但我们一眼了然,明显我们的最小值不是1,而是0,所以当array[low]、array[mid]、array[high]相等的时候,我们的程序并不知道应该如何移动,按照目前的移动方式就默认array[mid]在左边递增子数组了,这显然是不负责任的做法。
我们修正一下代码:
publicclassTest08{ publicstaticintgetTheMin(intnums[]){ if(nums==null||nums.length==0){ thrownewRuntimeException("inputerror!"); } //如果只有一个元素,直接返回 if(nums.length==1) returnnums[0]; intresult=nums[0]; intlow=0,high=nums.length-1; intmid=low; //确保low下标对应的值在左边的递增子数组,high对应的值在右边递增子数组 while(nums[low]>=nums[high]){ //确保循环结束条件 if(high-low==1){ returnnums[high]; } //取中间位置 mid=(low+high)/2; //三值相等的特殊情况,则需要从头到尾查找最小的值 if(nums[mid]==nums[low]&&nums[mid]==nums[high]){ returnmidInorder(nums,low,high); } //代表中间元素在左边递增子数组 if(nums[mid]>=nums[low]){ low=mid; }else{ high=mid; } } returnresult; } /** *查找数组中的最小值 * *@paramnums数组 *@paramstart数组开始位置 *@paramend数组结束位置 *@return找到的最小的数字 */ publicstaticintmidInorder(int[]nums,intstart,intend){ intresult=nums[start]; for(inti=start+1;i<=end;i++){ if(result>nums[i]) result=nums[i]; } returnresult; } publicstaticvoidmain(String[]args){ //典型输入,单调升序的数组的一个旋转 int[]array1={3,4,5,1,2}; System.out.println(getTheMin(array1)); //有重复数字,并且重复的数字刚好的最小的数字 int[]array2={3,4,5,1,1,2}; System.out.println(getTheMin(array2)); //有重复数字,但重复的数字不是第一个数字和最后一个数字 int[]array3={3,4,5,1,2,2}; System.out.println(getTheMin(array3)); //有重复的数字,并且重复的数字刚好是第一个数字和最后一个数字 int[]array4={1,0,1,1,1}; System.out.println(getTheMin(array4)); //单调升序数组,旋转0个元素,也就是单调升序数组本身 int[]array5={1,2,3,4,5}; System.out.println(getTheMin(array5)); //数组中只有一个数字 int[]array6={2}; System.out.println(getTheMin(array6)); //数组中数字都相同 int[]array7={1,1,1,1,1,1,1}; System.out.println(getTheMin(array7)); //特殊的不知道如何移动 int[]array8={1,0,1,1,1}; System.out.println(getTheMin(array8)); } }我们再用完善的测试用例放进去,测试通过。
总结
本题其实考察的点挺多的,实际上就是考察对二分查找的灵活运用,不少小伙伴死记硬背二分查找必须遵从有序,而没有学会这个二分查找的思想,这样会导致只能想到循环查找最小值了。
不少小伙伴在面试中表态,Android原生态基本都封装了常用算法,对面试这些无作用的算法表示抗议,其实这是相当愚蠢的。我们不求死记硬背算法的实现,但求学习到其中巧妙的思想。只有不断地提升自己的思维能力,才能助自己收获更好的职业发展。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。