{"id":4146,"date":"2018-10-02T19:28:58","date_gmt":"2018-10-03T02:28:58","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4146"},"modified":"2018-10-02T19:32:20","modified_gmt":"2018-10-03T02:32:20","slug":"leetcode-31-next-permutation","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-31-next-permutation\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 31. Next Permutation"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

Implement\u00a0next permutation<\/strong>, which rearranges numbers into the lexicographically next greater permutation of numbers.<\/p>\n

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).<\/p>\n

The replacement must be\u00a0in-place<\/a><\/strong>\u00a0and use only constant\u00a0extra memory.<\/p>\n

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.<\/p>\n

1,2,3<\/code>\u00a0\u2192\u00a01,3,2<\/code>
\n3,2,1<\/code>\u00a0\u2192\u00a01,2,3<\/code>
\n1,1,5<\/code>\u00a0\u2192\u00a01,5,1<\/code><\/p>\n

Solution<\/strong><\/h1>\n

Find the last acceding element x, swap with the smallest number y, y is after x that and y is greater than x.<\/p>\n

Reverse the elements after x.<\/p>\n

Time complexity: O(n)<\/p>\n

Space complexity: O(1)<\/p>\n

\n

C++<\/h2>\n
\n\n
\/\/ Author: Huahua, 8 ms\r\nclass Solution {\r\npublic:\r\n  void nextPermutation(vector<int>& nums) {\r\n    int i = nums.size() - 2;\r\n    while (i >= 0 && nums[i + 1] <= nums[i]) --i;\r\n    if (i >= 0) {\r\n      int j = nums.size() - 1;\r\n      while (j >= 0 && nums[j] <= nums[i]) --j;\r\n      swap(nums[i], nums[j]);\r\n    }\r\n    reverse(begin(nums) + i + 1, end(nums));\r\n  }\r\n};<\/pre>\n\n<\/div>
Python3<\/h2>\n
\n\n
# Author: Huahua, 48 ms\r\nclass Solution:\r\n  def nextPermutation(self, nums):\r\n    n = len(nums)\r\n    i = n - 2\r\n    while i >= 0 and nums[i] >= nums[i + 1]: i -= 1\r\n    if i >= 0:\r\n      j = n - 1\r\n      while j >= 0 and nums[j] <= nums[i]: j -= 1\r\n      nums[i], nums[j] = nums[j], nums[i]\r\n    nums[i + 1:] = nums[i+1:][::-1]<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
Problem Implement\u00a0next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[273,177,121,246],"class_list":["post-4146","post","type-post","status-publish","format-standard","hentry","category-array","tag-in-place","tag-medium","tag-permutation","tag-reverse","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4146","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4146"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4146\/revisions"}],"predecessor-version":[{"id":4150,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4146\/revisions\/4150"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4146"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4146"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4146"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}