{"id":2830,"date":"2020-01-30T14:45:35","date_gmt":"2020-01-30T06:45:35","guid":{"rendered":"http:\/\/www.sniper97.cn\/?p=2830"},"modified":"2020-01-30T14:45:35","modified_gmt":"2020-01-30T06:45:35","slug":"%e3%80%90leetcode%e3%80%910031-%e4%b8%8b%e4%b8%80%e4%b8%aa%e6%8e%92%e5%88%97","status":"publish","type":"post","link":"http:\/\/www.sniper97.cn\/index.php\/note\/algorithm\/2830\/","title":{"rendered":"\u3010LeetCode\u30110031 \u4e0b\u4e00\u4e2a\u6392\u5217"},"content":{"rendered":"\n<p><a href=\"https:\/\/leetcode-cn.com\/problems\/next-permutation\/\">https:\/\/leetcode-cn.com\/problems\/next-permutation\/<\/a><\/p>\n\n\n<pre class=\"wp-block-preformatted\"># -*- coding:utf-8 -*-<em>\n<\/em>class Solution:\n    def nextPermutation(self, nums):\n        <em>\"\"\"\n        Do not return anything, modify nums in-place instead.\n        \"\"\"\n        <\/em>firstIndex = -1\n        n = len(nums)\n        def reverse(nums, i, j):\n            <em>\"\"\"\n            \u7ffb\u8f6c\u5217\u8868\n            <\/em><strong><em>:param<\/em><\/strong><em> nums:\n            <\/em><strong><em>:param<\/em><\/strong><em> i:\n            <\/em><strong><em>:param<\/em><\/strong><em> j:\n            <\/em><strong><em>:return<\/em><\/strong><em>:\n            \"\"\"\n            <\/em>while i &lt; j:\n                nums[i], nums[j] = nums[j], nums[i]\n                i += 1\n                j -= 1\n        # \u6b63\u5e8f\u67e5\u627e\n        for i in range(n - 2, -1, -1):\n            if nums[i] &lt; nums[i + 1]:\n                firstIndex = i\n                break\n        # \u67e5\u627e\u4e0d\u5230\u76f4\u63a5\u7ffb\u8f6c\u8fd4\u56de\n        if firstIndex == -1:\n            reverse(nums, 0, n - 1)\n            return nums\n        # \u7ffb\u8f6c\u67e5\u627e\n        secondIndex = -1\n        for i in range(n - 1, firstIndex, -1):\n            if nums[i] > nums[firstIndex]:\n                secondIndex = i\n                break\n        # \u4ea4\u6362\u4e24\u6b21\u67e5\u627e\u7684\u7d22\u5f15\n        nums[firstIndex], nums[secondIndex] = nums[secondIndex], nums[firstIndex]\n        # \u7ffb\u8f6c\u56de\u6765\u8fd4\u56de\n        reverse(nums, firstIndex + 1, n - 1)\n        return nums\nif __name__ == '__main__':\n    nums = [1, 2, 3]\n    print(Solution().nextPermutation(nums))\n<\/pre>\n\n\n<p><strong>\u601d\u8def<\/strong>\uff1a\u8fd9\u9053\u9898\uff0c\u4e0d\u5f97\u4e0d\u8bf4\u592a\u5de7\u4e86\uff0c\u592a\u68d2\u4e86\uff0c\u5b66\u5230\u4e86\u5f88\u591a\u3002<\/p>\n\n\n<p>\u8fd9\u9053\u9898\u5c31\u662f\u627e\u6bd4\u5f53\u524d\u5927\u7684\u5b57\u5178\u5e8f\uff0c\u8fd9\u9053\u9898\u7684\u601d\u8def\u6bd4\u8f83\u5de7\u3002<\/p>\n\n\n<p>\u4e3e\u4e2a\u4f8b\u5b50\uff1a[1,2,4,6,5,2,1]<\/p>\n\n\n<p>\u9996\u5148\u4ece\u540e\u5411\u524d\u627e\u80fd\u591f\u5c06\u5f53\u524d\u5b57\u5178\u5e8f\u53d8\u5927\u7684\u4f4d\u7f6e\uff0c\u4e4b\u6240\u4ee5\u662f\u4ece\u540e\u5411\u524d\u627e\uff0c\u662f\u56e0\u4e3a\u8981\u627e\u5bf9\u5b57\u5178\u5e8f\u5f71\u54cd\u6700\u5c0f\u7684\u5143\u7d20\u3002\u6211\u4eec\u627e\u5230\u4e864\uff0c4\u4e4b\u540e\u7684\u5143\u7d20\u90fd\u662f\u964d\u5e8f\uff0c\u4e5f\u5c31\u662f\u8bf4\u5bf9\u4e8e4\u4e4b\u540e\u7684\u5143\u7d20\uff0c\u5df2\u7ecf\u6ee1\u8db3\u4e86\u6700\u5927\u5b57\u5178\u5e8f\u3002<\/p>\n\n\n<p>\u7136\u540e\u6211\u4eec\u627e\u5230\u4e86\u5f71\u54cd\u5b57\u5178\u5e8f\u7684\u7f6a\u9b41\u7978\u99964\uff0c\u5c31\u8981\u627e\u4ed6\u548c\u8c01\u4ea4\u6362\u5462\uff1f\u56e0\u4e3a\u6211\u4eec\u5e0c\u671b\u5b57\u5178\u5e8f\u7684\u589e\u52a0\u6bd4\u8f83\u5c0f\uff0c\u56e0\u6b64\u6211\u4eec\u7ee7\u7eed\u57284\u540e\u5012\u5e8f\u627e\u6bd44\u5927\u7684\u6570\uff0c\u56e0\u4e3a4\u540e\u5df2\u7ecf\u6ee1\u8db3\u964d\u5e8f\uff0c\u56e0\u6b64\u5012\u5e8f\u627e\u5230\u6bd44\u5927\u7684\u6570\u5c31\u662f\u6700\u5c0f\u7684\u6570\uff0c\u4e5f\u5c31\u662f\u80fd\u5f71\u54cd\u5b57\u5178\u5e8f\u6700\u5c0f\u7684\u6570\u5b575\u3002<\/p>\n\n\n<p>\u6211\u4eec\u5c064\u548c5\u4ea4\u6362\uff0c\u6b64\u65f6\u5217\u8868\u53d8\u6210 [1,2,5,6,4,2,1] <\/p>\n\n\n<p>\u8fd9\u65f6\u50195\u540e\u4f9d\u7136\u4fdd\u6301\u7740\u6700\u5927\u5b57\u5178\u5e8f\u7684\u72b6\u6001\uff0c\u6211\u4eec\u5c06\u5176\u7ffb\u8f6c\uff0c\u5230\u6700\u5c0f\u5b57\u5178\u5e8f\u3002 [1,2,5,1,2,4,6]  <\/p>\n\n\n<p>\u8fd9\u65f6\u5019\uff0c\u56e0\u4e3a5\u7684\u6539\u53d8\uff0c  [1,2,5,1,2,4,6]  \u7684\u5b57\u5178\u5e8f\u5c31\u662f [1,2,4,6,5,2,1] \u7684\u4e0b\u4e00\u4e2a\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/leetcode-cn.com\/problems\/next-permutation\/ [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_mi_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[10],"tags":[],"views":1432,"_links":{"self":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/2830"}],"collection":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/comments?post=2830"}],"version-history":[{"count":0,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/2830\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/media?parent=2830"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/categories?post=2830"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/tags?post=2830"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}