My python solution, no sort, o(n)


  • 0
    F

    firstly, reversely iterate to find the first number head (index i) that need to be swapped

    secondly, reversely iterate to find the number index j, bigger than head, than swap h and head

    thirdly, reverse the s[j::-1]

        if n > 2**31-1:
            return -1
        strN = str(n)
        
        headInd = -1
        for i in range(len(strN)-1, 0, -1):
            if strN[i-1] < strN[i]:
                headInd = i-1
                break
        if headInd == -1:
            return -1
        
        swapInd = headInd + 1
        for i in range(len(strN)-1, headInd+1, -1):
            if strN[i] > strN[headInd]:
                swapInd = i
                break
            #swap
        tmp = strN[:headInd] + strN[swapInd] + strN[headInd+1:swapInd] + strN[headInd] + strN[swapInd+1:]
        #reverse
        ans = int(tmp[:headInd+1] + tmp[headInd+1:len(strN)][::-1])
        return -1 if ans > 2**31-1 else ans

Log in to reply
 

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