lintcode-1174.下一个更大的元素 III

题目描述：

1174. 下一个更大的元素 III

给定一个32位整数n，用同样的数字组成新的32位整数，使得它要比n大，返回最小的这样的数。如果不存在这样的整数，返回-1。

算法思路：

首先将这个数转化成list数组，从后往前判断list数组后一位大于前一位数的index，记录下此index。根据index将原数组拆分成两部分，将前面部分保留，查找后半部分的数组中比第一个元素更大的数，记录下此数并在后半部分列表中删除，将删除后的列表进行排序。最终查找结果为前半部分列表+删除的数（列表形式）+后半部分列表。

code

class Solution:

    """

    @param n: an integer

    @return: the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n

    """

    def nextGreaterElement(self, n):

        # Write your code here

        list_n = list(str(n))

        length_n = len(list_n)

        if length_n == 1: #如果list长度为1，则不存在

            return -1

        index = -1

        while list_n[index] <= list_n[index-1]: #从list最后一个数开始比较

            index -= 1

            if index == -length_n: #如果已经是按照由大到小顺序排列，则不存在

                return -1

        #后半部分数组

        res_list = list_n[index-1:]

        replace = 0

        for num in sorted(res_list):

            if num > res_list[0]:

                replace = num

                break

        res_list.remove(replace)

        result = list_n[:index-1] + [replace] + sorted(res_list)

        result_n = int(''.join(str(i) for i in result))

        #判断输出的数的范围是32位整数范围

        if result_n >= -2147483648 and result_n <= 2147483647:

            return result_n

        else:

            return -1

巴特西

lintcode-1174.下一个更大的元素 III

1174. 下一个更大的元素 III

最新文章

热门文章