<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 0060. 第k個排列 ## 題目地址(60. 第k個排列) <https://leetcode-cn.com/problems/permutation-sequence/> ## 題目描述 ``` <pre class="calibre18">``` 給出集合 [1,2,3,…,n],其所有元素共有 n! 種排列。 按大小順序列出所有排列情況,并一一標記,當 n = 3 時, 所有排列如下: "123" "132" "213" "231" "312" "321" 給定 n 和 k,返回第 k 個排列。 說明: 給定 n 的范圍是 [1, 9]。 給定 k 的范圍是[1, n!]。 示例 1: 輸入: n = 3, k = 3 輸出: "213" 示例 2: 輸入: n = 4, k = 9 輸出: "2314" ``` ``` ## 前置知識 - 數學 - 回溯 - factorial ## 公司 - 阿里 - 百度 - 字節 - Twitter ## 題目描述 ``` <pre class="calibre18">``` 給出集合 [1,2,3,…,n],其所有元素共有 n! 種排列。 按大小順序列出所有排列情況,并一一標記,當 n = 3 時, 所有排列如下: "123" "132" "213" "231" "312" "321" 給定 n 和 k,返回第 k 個排列。 說明: 給定 n 的范圍是 [1, 9]。 給定 k 的范圍是[1, n!]。 示例 1: 輸入: n = 3, k = 3 輸出: "213" 示例 2: 輸入: n = 4, k = 9 輸出: "2314" ``` ``` ## 思路 LeetCode 上關于排列的題目截止目前(2020-01-06)主要有三種類型: - 生成全排列 - 生成下一個排列 - 生成第 k 個排列(我們的題目就是這種) 我們不可能求出所有的排列,然后找到第 k 個之后返回。因為排列的組合是 N!,要比 2^n 還要高很多,非常有可能超時。我們必須使用一些巧妙的方法。 我們以題目中的 n= 3 k = 3 為例: - "123" - "132" - "213" - "231" - "312" - "321" 可以看出 1xx,2xx 和 3xx 都有兩個,如果你知道階乘的話,實際上是 2!個。 我們想要找的是第 3 個。那么我們可以直接跳到 2 開頭,我們排除了以 1 開頭的排列,問題縮小了,我們將 2 加入到結果集,我們不斷重復上述的邏輯,知道結果集的元素為 n 即可。 ## 關鍵點解析 - 找規律 - 排列組合 ## 代碼 - 語言支持: Python3 ``` <pre class="calibre18">``` <span class="hljs-keyword">import</span> math <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">getPermutation</span><span class="hljs-params">(self, n: int, k: int)</span> -> str:</span> res = <span class="hljs-string">""</span> candidates = [str(i) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n + <span class="hljs-params">1</span>)] <span class="hljs-keyword">while</span> n != <span class="hljs-params">0</span>: facto = math.factorial(n - <span class="hljs-params">1</span>) <span class="hljs-title"># i 表示前面被我們排除的組數,也就是k所在的組的下標</span> <span class="hljs-title"># k // facto 是不行的, 比如在 k % facto == 0的情況下就會有問題</span> i = math.ceil(k / facto) - <span class="hljs-params">1</span> <span class="hljs-title"># 我們把candidates[i]加入到結果集,然后將其彈出candidates(不能重復使用元素)</span> res += candidates[i] candidates.pop(i) <span class="hljs-title"># k 縮小了 facto * i</span> k -= facto * i <span class="hljs-title"># 每次迭代我們實際上就處理了一個元素,n 減去 1,當n == 0 說明全部處理完成,我們退出循環</span> n -= <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> res ``` ``` **復雜度分析** - 時間復雜度:O(N2)O(N^2)O(N2) - 空間復雜度:O(N)O(N)O(N) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看