LeetCode 31: Next Permutation

tags: Array

---

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, do not allocate extra memory.

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

Function:

public void nextPermutation(int[] nums) {
    // Your Code
}

---

题目分析

该题目是C++ STL中实现的next_permutation()的变种，要求根据当前的nums序列，返回下一个排列，例子如题目中所述。解题思路如下，图片来源于fisherlei的博客。

算法：自己的实现

public void nextPermutation(int[] nums) {
    if (nums==null || nums.length<2)
        return;
    int pos = nums.length - 1;
    for (; pos>0; pos--) { // 寻找第一个转折点x
        if (nums[pos] > nums[pos-1]) {
            break;
        }
    }
    pos--; // 转折点在pos-1出，因此这里pos--
    if (pos >= 0) { // 如果转折点在数组内
        int index = nums.length - 1;
        while (index > pos) {
            if (nums[index] > nums[pos]) { // 1.找到第一个大于nums[pos]，并交换
                swap(nums, pos, index);
                break;
            }
            index--;
        }
    }
    reverseSort(nums, pos+1); // 2.对转折点之后的数组进行反转排序
}

private void swap(int[] nums, int i, int j) { // 3.相同操作抽象成方法调用
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

private void reverseSort(int[] nums, int start) {
    if (start >= nums.length-1)
        return;
    int len = (start+nums.length)/2;
    int temp;
    for (int i=start; i<len; i++) {
        int other = start+nums.length-1-i;
        swap(nums, i, other);
    }
}

该算法通过逆序遍历，找到第一个转折点并记录其位置pos，如果pos<0，说明整个数组已达到最大的逆序，只需要逆序重排即可；否则从pos+1到n中查找大于nums[pos]的最小值并记录其位置index，交换两者的位置，并对[pos+1,n)进行逆序重排即可。可以看到，整个算法的时间复杂度为O(n)，空间复杂度为O(1)，满足题目要求。以下是本题目解决过程中需要注意的地方：

1. 数组类型的算法中，数组元素的排列通常具有一定的规律，充分利用这些规律能够大大简化解题方法、提升算法效率。如本算法中，在pos之后的数组应该是一个降序的排列，因此只需要顺序遍历找到第一个大于nums[pos]的元素即可；
2. 同第1条，虽然在这里两者进行了置换，但原nums[pos]放到新的位置，仍然满足nums[pos+1,n)降序排列，因此reverseSort方法仍然适用。
3. 在本题中大量用到swap、reverseSort，自己在以后的编码中应该将这些过程抽象成方法，能够提高算法的简洁度。