Topic Description (Medium Difficulty)

I think half the difficulty of this problem is understanding the meaning of the question. You are given a number, and then you rearrange the numbers to get a number that is just larger than the original number. If no number is larger than the original number, the output is in ascending order.

The point is what exactly does that mean? Let’s say the original number is A, and then we rearrange each of the original numbers to produce B, C, D, E, and then we arrange the five numbers from the smallest to the largest, such as D, A, B, E, and C, and then we’re looking for B, the number that’s just bigger than A.

If we have 123, and we have 132, 213, 231, 312,321, and we go from smallest to largest, 123, 132, 213, 231, 312, 321, we’re looking for 132.

And they also want the space complexity to be order 1.

A # method

Let’s think about a few questions.

To make the number bigger, all you have to do is make any digit bigger.

To get a number that’s just bigger, you have to change the ones place.

If I make it bigger, I can only swap.

If you start with the ones place, and you go from right to left, and you find something bigger than the ones place, and you swap it over, the ones place gets swapped over to a higher place, because the ones place is smaller, so even though the ones place gets bigger, the whole number gets smaller. So 1, 3, 2, if YOU swap the 2 and the 3, you get 1, 2, 3, the ones place gets bigger, but the whole number gets smaller.

The ones place doesn’t work, so if we go to the tens place, if we take a larger number to the left of the tens place and switch it over, it’s the same thing as the ones place, it’s going to get smaller. For example, 4, 1, 2, 3, if YOU swap 2 with 4, 2, 1, 4, 3, the numbers will get smaller. If you take a larger number from the right and swap it, because you’re swapping it from the lower order, it’s going to get bigger. So 4, 1, 2, 3, switch the 2 and the 3, you get a 4, 1, 3, 2 and the numbers get bigger.

If there’s nothing to the right of the tens place that’s bigger than the tens place, we move to the left and we look to the next place, and we look to the right of the current place, and we see if there’s a bigger number, and if there’s nothing to the right, we just keep moving to the left.

One more question, if there’s more than one digit on the right which one is greater than the current bit? Select the one that is just larger than the current bit, so that the overall number is as small as possible.

Is the exchange over? Don’t. Because the numbers get bigger, but not necessarily just bigger than the original numbers. For example, 158476531, we start in the tens place, and nothing on the right-hand side is greater than 3. If we look at the hundreds place, we don’t have anything to the right of the hundreds place greater than 5. All the way up to 4, there’s a lot of stuff on the right-hand side that’s greater than 4, so pick the one that’s just greater than 4, which is 5. And then we switch, and it becomes 158576431, so the number is bigger, but it’s not just bigger than 158476531, and we need to sort the numbers to the right of 5 from the smallest to the largest. It becomes 158513467, and we’re done.

And for the final sort, we don’t really need to use the sort function, because the number to the right of the 5 must be in descending order, we just need to reverse order. Take a look at the GIF provided by LeetCode to help you understand.

If we look at this process, we actually go from right to left to find the position where the first digit is no longer increasing, and then from right to find a digit that is just larger than the current digit.

Let’s look at the code again.

public void nextPermutation(int[] nums) {
    int i = nums.length - 2;
    // Find the first position that is not incremented
    while (i >= 0 && nums[i + 1] <= nums[i]) {
        i--;
    }
    // If you get to the far left, print it upside down
    if (i < 0) {
        reverse(nums, 0);
        return;
    }
    // Find the position just greater than nums[I]
    int j = nums.length - 1;
    while (j >= 0 && nums[j] <= nums[i]) {
        j--;
    }
    / / exchange
    swap(nums, i, j);
    // use inversion to sort
    reverse(nums, i + 1);

}

private void swap(int[] nums, int i, int j) {
    int temp = nums[j];
    nums[j] = nums[i];
    nums[i] = temp;
}

private void reverse(int[] nums, int start) {
    int i = start, j = nums.length - 1;
    while(i < j) { swap(nums, i, j); i++; j--; }}Copy the code

Time complexity: The worst-case scenario is that all the bits are iterated, O (n), inverted is also O (n), so the total is still O (n).

Space complexity: O (1).

The total

At the beginning, I did not understand the problem. Later, AFTER understanding the problem, I tried several but failed to figure it out. Then, I read the Solution and clarified my thinking.

See Leetcode.Wang for more details on popular problems.