程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode Next Permutation

LeetCode Next Permutation

編輯:C++入門知識

LeetCode Next Permutation


LeetCode解題之Next Permutation


原題

找出一個數組按字典序排列的後一種排列。

注意點:

如果原來就是字典序排列中最大的,將其重新排列為字典序最小的排列 不要申請額外的空間 小心數組越界問題 函數沒有返回值,直接修改列表

例子:

輸入: [1,2,3]
輸出: [1,3,2]

輸入: [3,2,1]
輸出: [1,2,3]

解題思路

通過一個例子來說明,原數組為[1,7,3,4,1]。我們想要找到比173421大一點的數,那就要優先考慮將後面的數字變換順序,而421從後往前是升序的(也就是這三個數字能組成的最大的數),變換了反而會變小,所以要先找到降序的點。可以看出3是第一個降序的點,要想整個數變大,3就要變大,從後往前找到第一個比3大的數4,將3和4交換位置得到174321,既然原來3所在位置的數字變大了,那整個數肯定變大了,而它之後的數是最大的(從後往前是升序的),應轉換成最小的,直接翻轉。

AC源碼

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        length = len(nums)

        targetIndex = 0
        changeIndex = 0
        for i in range(length - 1, 0, -1):
            if nums[i] > nums[i - 1]:
                targetIndex = i - 1
                break
        for i in range(length - 1, -1, -1):
            if nums[i] > nums[targetIndex]:
                changeIndex = i
                break
        nums[targetIndex], nums[changeIndex] = nums[changeIndex], nums[targetIndex]
        if targetIndex == changeIndex == 0:
            nums.reverse()
        else:
            nums[targetIndex + 1:] = reversed(nums[targetIndex + 1:])

歡迎查看我的Github來獲得相關源碼。


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved