Sharing my really simple solution with explanation


  • 23
    Z
    void nextPermutation(vector<int> &num) {
        for(int i = num.size() - 2; i >= 0; i--){
            if(num[i] < num[i + 1]){
                int pos;
                int diff = INT_MAX;
                for(int j = i + 1; j < num.size(); j++){
                    if(num[j] > num[i] && abs(num[i] - num[j]) < diff){
                        diff = abs(num[i] - num[j]);
                        pos = j;
                    }
                }
                swap(num[i], num[pos]);
                sort(num.begin() + i + 1, num.end());
                return;
            }
        }
        sort(num.begin(), num.end());
    }
    

    For this problem, coding is not a big deal. Algorithm is!

    Now let's pick a number, for example, 24387651.

    what is the next permutation? 24513678.

    How can I get the answer?

    First step: find the first ascending digit from the back of the number. 3 < 8 > 7 > 6 > 5 > 1. Then 3 is the digit.

    Second step: swap that digit with the next big digit in following digits. Which one is the next big digit in 87651? 5! So swap them. Now the number becomes 24587631.

    Third step: sort 87631 into 13678. The final answer is 24513678.


  • 1
    Z
    void nextPermutation(vector<int> &num) {
        for(int i = num.size() - 2; i >= 0; i--){
            if(num[i] < num[i + 1]){
                int pos;
                for(int j = num.size() - 1; j > i; ++j){// the digits from i+1 to end is already ascending
                    if(num[j] > num[i]){
                        pos = j;
                        break;
                    }
                }
                swap(num[i], num[pos]);
                sort(num.begin() + i + 1, num.end());
                return;
            }
        }
        sort(num.begin(), num.end());
    }
    

    question: i. to locate the the next big digit in following digits, means you need find out the index j that num[j] is bigger than num[i], the digits from i+1 to end is already ascending, why you don't use it ?


  • 0
    S

    Good explanation!


  • 0
    M

    Actually, the sort() is not necessary, because after swapping, the left thing to do is to reverse the remaining array after the element get swapped. And this reversing only calls for O(n).


  • 0
    D

    think again, in this specific case all numbers are in descending order except first three number. after swap in step 1, you cannot guarantee we have such descending numbers left. So sort is necessary.


  • 0
    W

    I think the left thing has to be descending order, otherwise you find the wrong "first ascending digit" in step one.


  • 0
    L

    ritght ,just reverse.


  • 0
    S

    very good explanation!


  • 0
    Y

    Sort is necessary.
    Consider this case, input is 2, 3, 1, 3, 3.
    First step, find the 1. Second swap 1 with next element larger than 1, we get 2, 3, 3, 1, 3. Then if we reverse last 2 elements "1,3", we get 2, 3, 3, 3, 1. If we sort the last 2 element "1, 3", we get 2, 3, 3, 1, 3. The correct answer is 2, 3, 3, 1, 3. So, we must use SORT instead of REVERSE! If you use reverse, you will fail the above test case.


  • 0
    O

    sort is not necessary, first step find 1, second step find the next element larger than 1, if have duplicate, use the rightmost one, swap with 1, get 2, 3, 3,3,1, then do the reverse, get 2,3,3,1,3. The point is if there is duplicate, swap with rightmost one.


  • 1
    L

    Please refer to this wiki https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
    It's same algorithm as described in above wiki, which is introduced by Narayana Pandita in 14th century


  • 0

    Nice solution! Here comes the Java codes using your idea:

    public void nextPermutation(int[] nums) {
            if (nums == null || nums.length <= 1) return;
            for (int i = nums.length - 2; i >= 0; i--) {
                if (nums[i] < nums[i+1]) {
                    int min = nums[i+1], index = i + 1;
                    for (int j = i + 1; j < nums.length; j++) {
                        if (nums[j] < min && nums[j] > nums[i]) {
                            index = j;
                            min = nums[j];
                        }
                    }
                    nums[index] = nums[i];
                    nums[i] = min;
                    Arrays.sort(nums, i+1, nums.length);
                    return;
                }
            }
            Arrays.sort(nums);
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.