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中實(shí)現(xiàn)的next_permutation()的變種，要求根據(jù)當(dāng)前的nums序列，返回下一個(gè)排列，例子如題目中所述。解題思路如下，圖片來源于fisherlei的博客。

算法：自己的實(shí)現(xiàn)

public void nextPermutation(int[] nums) {
    if (nums==null || nums.length<2)
        return;
    int pos = nums.length - 1;
    for (; pos>0; pos--) { // 尋找第一個(gè)轉(zhuǎn)折點(diǎn)x
        if (nums[pos] > nums[pos-1]) {
            break;
        }
    }
    pos--; // 轉(zhuǎn)折點(diǎn)在pos-1出，因此這里pos--
    if (pos >= 0) { // 如果轉(zhuǎn)折點(diǎn)在數(shù)組內(nèi)
        int index = nums.length - 1;
        while (index > pos) {
            if (nums[index] > nums[pos]) { // 1.找到第一個(gè)大于nums[pos]，并交換
                swap(nums, pos, index);
                break;
            }
            index--;
        }
    }
    reverseSort(nums, pos+1); // 2.對(duì)轉(zhuǎn)折點(diǎn)之后的數(shù)組進(jìn)行反轉(zhuǎn)排序
}

private void swap(int[] nums, int i, int j) { // 3.相同操作抽象成方法調(diào)用
    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);
    }
}

該算法通過逆序遍歷，找到第一個(gè)轉(zhuǎn)折點(diǎn)并記錄其位置pos，如果pos<0，說明整個(gè)數(shù)組已達(dá)到最大的逆序，只需要逆序重排即可；否則從pos+1到n中查找大于nums[pos]的最小值并記錄其位置index，交換兩者的位置，并對(duì)[pos+1,n)進(jìn)行逆序重排即可?？梢钥吹剑麄€(gè)算法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)，滿足題目要求。以下是本題目解決過程中需要注意的地方：

1. 數(shù)組類型的算法中，數(shù)組元素的排列通常具有一定的規(guī)律，充分利用這些規(guī)律能夠大大簡化解題方法、提升算法效率。如本算法中，在pos之后的數(shù)組應(yīng)該是一個(gè)降序的排列，因此只需要順序遍歷找到第一個(gè)大于nums[pos]的元素即可；
2. 同第1條，雖然在這里兩者進(jìn)行了置換，但原nums[pos]放到新的位置，仍然滿足nums[pos+1,n)降序排列，因此reverseSort方法仍然適用。
3. 在本題中大量用到swap、reverseSort，自己在以后的編碼中應(yīng)該將這些過程抽象成方法，能夠提高算法的簡潔度。