31. Next Permutation

二刷 06/2022

Time O(N)

Space O(1)

Runtime: 2 ms, faster than 20.22% of Java online submissions for Next Permutation.

Memory Usage: 43.9 MB, less than 33.93% of Java online submissions for Next Permutation.

class Solution {

    public void nextPermutation(int[] nums) {

        // We've noticed that if a subarray is in descending order, then it's already the largest representative of such array

        // So from the right to left hand side, we need to find out nums[i - 1] < nums[i]

        // There's no larger arrangement on the right handside of nums[i - 1]

        // So we need to rearrange number from nums[i -1] to the end

        if (nums == null || nums.length == 0) {

            return;

        }

        int i = 0;

        for (i = nums.length - 1; i > 0; i--) {

            if (nums[i - 1] < nums[i]) {

                break;

            }

        }

        if (i > 0) {

            // Find the smallest number larger than nums[i - 1] from the right handside

            int j = nums.length - 1;

            while (nums[j] <= nums[i - 1]) {

                j--;

            }

            // System.out.printf("i - 1=%d, j=%d", i - 1, j);

            swap(nums, i - 1, j);

        }

        // Now we have nums[i - 1] in the right place

        // We want all numbers to the right of nums[i - 1] be in the smallest order

        // Since nums[i] to the end are already sorted in descending order, we just need to reverse them

        reverse(nums, i, nums.length - 1);

    }

    

    private void swap(int[] nums, int i, int j) {

        int temp = nums[i];

        nums[i] = nums[j];

        nums[j] = temp;

    }

    

    private void reverse(int[] nums, int start, int end) {

        while (start < end) {

            swap(nums, start, end);

            start++;

            end--;

        }

    }

}

一刷

1We need to increase one bit -> we want this bit as right as possible

2Traverse from right to left, if everything is in increasing order, means currently they are the largest combination for those digits

3The 1st decreasing bit we see will be the one that needs to be increased

4We want this bit to increase but increase as small as possible, we need to choose the smallest number from its right side

e.g.  2 3 1

We swap 2&3 -> got 3 2 1

This is not the next value

After we swap and increased the right most bit, we need all its right bits to be as small as possible

That's why we are sorting nums [I + 1, len - 1)

85.19 %
class Solution {
    public void nextPermutation(int[] nums) {
// Find the first decreasing index
if (nums == null || nums.length < 2) {
return;
}
int len = nums.length;
int i = len - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
continue;
}
if (i == -1) {
Arrays.sort(nums);
return;
}
int min = -1;
// 1 3 2
for (int j = len - 1; j >= i + 1; j--) {
if (nums[j] > nums[i] && (min == -1 || nums[j] < nums[min])) {
min = j;
}
}
swap(nums, i, min);
Arrays.sort(nums, i + 1, len);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}