search

halfrost / LeetCode-Go

✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% / LeetCode 题解
https://books.halfrost.com/leetcode
MIT License
32.98k stars 5.7k forks source link

Update 31. Next Permutation : Provided detailed explanation, Slice is already a reference type, so In my opinion, no need to use pointer on both swap and reverse utility functions. #179

Closed ashtishad closed 3 years ago

ashtishad commented 3 years ago

Testcase: [2,3,6,5,4,1]

Algorithm:

  1. from right to left, find the first decreasing number. In this case which is 3. Here we have two cases. Case 1: If not found, that means it already on it's last permutation .So, reverse all of it's number to get back to original state. Case 2: If found, we will start from right most to leftward, try to find the first number which is larger than 3, in this case it is 4. Then we swap 3 and 4, the list turn to 2,4,6,5,3,1. Last, we reverse numbers on the right of 4, we finally get 2,4,1,3,5,6.