Shortest Solution Handle Ascended & Descended Cases (Symmetric)


  • 0
    H
    class Solution:
        # @param num, a list of integer
        # @return an integer
        def findMin(self, num):
        # ascending:  0 1 2 3 4 5 6 7 ----> 4 5 6 7 0 1 2 3, edge case no rotation: 0 1 2 3 4 5 6 7, interesting case 0 1 --> 1 0
        # descending: 7 6 5 4 3 2 1 0  ---> 4 3 2 1 0 7 6 5, edge case no rotation: 7 6 5 4 3 2 1 0, interesting case 1 0 --> 0 1
            if not num:
                return None  # or return maxint, since the list is empty
            L, R = 0, len(num)-1
            if num[L] > num[R]:
                 #handle cases (I) original acsending & rotated [5,6,7,0,1,2,3,4] (II) original descending & no-rotation [7,6,5,4,3,2,1,0]
                while L < R:
                    M = (L+R)//2
                    if num[M] < num[R]: #note do NOT compare with num[L] as when R=L+1, we have M=L and need to avoid compare with itself
                        R = M
                    else:
                        L = M + 1
            else:
                # code copied from ascending case, but logically reverse the array 
                 while L < R:
                    M = (L+R+1)//2
                    if num[M] < num[L]: #do NOT compare with num[R] as when R=L+1, we have M=L and need to avoid compare with itself
                        L = M
                    else:
                        R = M - 1
            return num[L]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.