LeetCode031-Next Permutation-

Next Permutation

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).

The replacement must be in-place and use only constant extra memory.

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

解法代码

import java.util.Arrays;

public class LeetCode31 {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3};
        System.out.print("Array string : " + Arrays.toString(nums));
        new LeetCode31().nextPermutation(nums);
        System.out.println(",nextPermutation: " + Arrays.toString(nums));
        nums = new int[]{3, 2, 1};
        System.out.print("Array string : " + Arrays.toString(nums));
        new LeetCode31().nextPermutation(nums);
        System.out.println(",nextPermutation: " + Arrays.toString(nums));
        nums = new int[]{1, 1, 5};
        System.out.print("Array string : " + Arrays.toString(nums));
        new LeetCode31().nextPermutation(nums);
        System.out.println(",nextPermutation: " + Arrays.toString(nums));
        nums = new int[]{5, 3, 4, 2, 1};
        System.out.print("Array string : " + Arrays.toString(nums));
        new LeetCode31().nextPermutation(nums);
        System.out.println(",nextPermutation: " + Arrays.toString(nums));
        nums = new int[]{1, 3, 2};
        System.out.print("Array string : " + Arrays.toString(nums));
        new LeetCode31().nextPermutation(nums);
        System.out.println(",nextPermutation: " + Arrays.toString(nums));
        nums = new int[]{4, 2, 0, 2, 3, 2, 0};
        System.out.print("Array string : " + Arrays.toString(nums));
        new LeetCode31().nextPermutation(nums);
        System.out.println(",nextPermutation: " + Arrays.toString(nums));
        nums = new int[]{2, 2, 3, 4, 2, 3, 1, 1, 2};
        System.out.print("Array string : " + Arrays.toString(nums));
        new LeetCode31().nextPermutation(nums);
        System.out.println(",nextPermutation: " + Arrays.toString(nums));
        nums = new int[]{1, 1};
        System.out.print("Array string : " + Arrays.toString(nums));
        new LeetCode31().nextPermutation(nums);
        System.out.println(",nextPermutation: " + Arrays.toString(nums));
    }
    
    public void nextPermutation(int[] nums) {
        // 空数组和只有一个元素的数组，直接返回
        if(nums == null || nums.length < 2) {
            return;
        }
        int i = nums.length - 2;
        // 从后往前找，数据增大则跳过，如果发现数据变小，则说明找到了更大的排列
        while(i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        // If such arrangement is not possible, 
        // it must rearrange it as the lowest possible order
        // 没有找到解，元素全部反转
        if(i == -1) {
            reverse(nums, 0);
            return;
        }
        int j = i + 1;
        // 因为i后面的元素是有序的，利用反转对i后面的元素进行排序
        reverse(nums, j);
        // 找到数据交换的位置
        while(nums[j] <= nums[i]) {
            j++;
        }
        swap(nums, i, j);
    }
    
    private void reverse(int[] nums , int start) {
        int i = start;
        int j = nums.length - 1;
        while(i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

Output：

Array string : [1, 2, 3],nextPermutation: [1, 3, 2]
Array string : [3, 2, 1],nextPermutation: [1, 2, 3]
Array string : [1, 1, 5],nextPermutation: [1, 5, 1]
Array string : [5, 3, 4, 2, 1],nextPermutation: [5, 4, 1, 2, 3]
Array string : [1, 3, 2],nextPermutation: [2, 1, 3]
Array string : [4, 2, 0, 2, 3, 2, 0],nextPermutation: [4, 2, 0, 3, 0, 2, 2]
Array string : [2, 2, 3, 4, 2, 3, 1, 1, 2],nextPermutation: [2, 2, 3, 4, 2, 3, 1, 2, 1]
Array string : [1, 1],nextPermutation: [1, 1]

Time And Space Complexity

Time: 在最坏的情况下，只需要对整个数组进行两次扫描
Space: 不需要使用额外的存储空间，原地替换

Tips

关键点：

• 从后往前遍历元素，如果元素是增大或者相等的则跳过，如果出现一个变小的元素则说明，这个就是解的位置，假定为index，如下图（图中index的值为i-1）：

  
  

• 如果全部元素遍历完，都是递增或者是相等的，则说明没有更小排列，反转数组，直接返回

• 对数组index后的元素进行递增排序，即对原数组index后的元素做反转

• 在index后寻找第一个大于第index处的元素，与index位置的元素交换

求解过程可以参考下图，下图中第三步与第四步交换了次序：

/**
  *  一开始，不太优雅的实现代码，供反思
  */
public void nextPermutation(int[] nums) {
        // 空数组和只有一个元素的数组，直接返回
        if(nums == null || nums.length < 2) {
            return;
        }
        // 用于标记是否只需要重新排序即可
        boolean flag = false;
        // 数据交换点
        int index = nums.length - 1;
        // 从后往前找，数据增大则跳过，如果发现数据变小，则说明找到了更大的排列
        for(int i = index - 1; i >= 0; i--) {
            if(nums[i] > nums[i + 1]) {
                if(i == 0) {
                    flag = true;
                }
            }
            // 找到更大的排列
            if(nums[i] < nums[i + 1]){
                index = i;
                break;
            }
        }
        if(flag) {
            //If such arrangement is not possible, 
            //it must rearrange it as the lowest possible order
            Arrays.sort(nums);
            return;
        }
        if(nums.length - index > 1) {
            Arrays.sort(nums, index + 1, nums.length);
        }
        for(int j = index + 1; j < nums.length; j++) {
            if(nums[j] > nums[index]) {
                int tmp = nums[index];
                nums[index] = nums[j];
                nums[j] = tmp;
                break;
            }
        }
        
    }