Next Permutation II 190

Question

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

Example

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

Challenge

The replacement must be in-place, do not allocate extra memory.

Solution

思想基本和I一样。

首先找到需要变大的那一位。因为求的是next permutation，所以增大位数要尽量靠右边同时增大的数值要尽量小。具体方法如下：

1) 从数组尾部开始，依次找每一位数离它最近的比它小的数的位置（即要变大的位置），记录下这个数和离它最近的比它小的数的index。每一位数得到的结果都和之前保存的结果做比较，保留index最大的要变大的位置和找到这个位置的数的位置，当要变大的位置相同时，保留数值较小的找到这个位置的数的位置。

2) 遍历完整个数组后，根据得到的结果，将要变大位置的数和找到这个位置的数交换位置，并返回变大的位置

3) 将数组从变大的位置的后一位开始从小到大排序即可。这里因为要求inplace所以用了bubble sort，若可以用额外空间还能用更快的排序方法。

代码如下：

public class Solution {
    /**
     * @param nums: an array of integers
     * @return: return nothing (void), do not return anything, modify nums in-place instead
     */
    public void nextPermutation(int[] nums) {
        // write your code here
        if(nums == null || nums.length == 0){
            return;
        }

        int index = findMax(nums);

        bubbleSort(nums, index + 1, nums.length - 1);
    }

    private int findMax(int[] nums){
        int[] temp = new int[]{-1, -1};
        for(int i = nums.length - 1; i >= 0; i--){
            for(int j = i - 1; j >= 0; j--){
                if(nums[i] > nums[j]){
                    if(j > temp[0]){
                        temp[0] = j;
                        temp[1] = i;
                    }else if(j == temp[0]){
                        if(nums[i] < nums[temp[1]]){
                            temp[1] = i;
                        }
                    }
                    break;
                }
            }
        }
        if(temp[0] == -1){
            return -1;
        }
        int a = nums[temp[0]];
        nums[temp[0]] = nums[temp[1]];
        nums[temp[1]] = a;
        return temp[0];
    }

    private void bubbleSort(int[] nums, int start, int end){
        for(int i = start; i < end; i++){
            for(int j = start; j < end; j++){
                if(nums[j] > nums[j + 1]){
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
    }
}