首页 > 其他 > 详细

剑指offer:二分

时间:2021-02-20 09:46:56      阅读:29      评论:0      收藏:0      [点我收藏+]

题目:

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
 
这道题考的是二分法,二分明早再来复盘一下
 
 
 
 
 
 

错误答案:

这是我的错误答案,有好几处

?:if...elif...else写成了if...if...else

?:mid的计算方式不对,写成了=right/2,应该是(left+right)作为分子;且式子位置不对,应当写在while里面,因为while里需要用到mid给左右两个值赋值,如果写在外面那么mid就永远不会变了。还有一点就是除法写成//才是向下取整,不然python认为01是浮点数,除出来的结果是浮点型不能作为下标赋值给mid(这个错误经常报)

?:忘记了给while一个终止return

?:while条件不应该写等号

?:还有就是情况考虑不周全,认为下式成立就可以终止条件输出了,其实不是,如果是11101的情况,那么就会输出1而不是0;这种情况只好固定right,让left继续往后走,逐个和固定的right比较,而且因为while left<right才会进行代码块,所以移动过程中是左一直往右和右比较。

rotateArray[mid]=rotateArray[right]
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if len(rotateArray)==0:
            return 0
        if len(rotateArray)==1:
            return rotateArray[0]
        else:
            left=0
            right=len(rotateArray)-1
            mid=right/2
            while left<=right:
                if rotateArray[mid]<rotateArray[right]:
                    right=mid
                if rotateArray[mid]>rotateArray[right]:
                    left=mid+1
                else:
                    return rotateArray[mid]

所以正确答案如下:

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if len(rotateArray)==0:
            return 0
        elif len(rotateArray)==1:
            return rotateArray[0]
        else:
            left=0
            right=len(rotateArray)-1
            while left<right:
                mid=(left+right)//2
                if rotateArray[mid]<rotateArray[right]:
                    right=mid
                elif rotateArray[mid]>rotateArray[right]:
                    left=mid+1
                else:
                    left+=1
            return rotateArray[left]

 

剑指offer:二分

原文:https://www.cnblogs.com/liuxiangyan/p/14418845.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!