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

LeetCode Permutation Sequence

編輯:關於C++

LeetCode解題之Permutation Sequence


原題

找出由[1,2,3…n]中所有數字組成的序列中第k大的。

注意點:

n為1-9中某一個數字

例子:

輸入: n = 3, k = 3
輸出: “213”

解題思路

因為n個不同的數字可以組成n!個序列,那麼首位確定的序列都有(n-1)!種不同的可能性,而且這些序列都根據首位的大小進行了分組,1…是最小的(n-1)!個,2…是(n-1)!+1到2(n-1)!個,那麼現在只需要計算k中有幾個(n-1)!就可以確定首位的數字,同樣可以通過這樣的方法來確定第二位、第三位……此外,由於列表下標從0開始,所以k要減去1。

AC源碼

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        k -= 1
        factorial = 1
        for i in range(1, n):
            factorial *= i

        result = []
        array = list(range(1, n + 1))
        for i in range(n - 1, 0, -1):
            index = k // factorial
            result.append(str(array[index]))
            array = array[:index] + array[index + 1:]
            k %= factorial
            factorial //= i
        result.append(str(array[0]))
        return "".join(result)


if __name__ == "__main__":
    assert Solution().getPermutation(3, 3) == "213"
    assert Solution().getPermutation(9, 324) == "123685974"
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved