leetcode31 Next Permutation

題目要求

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.

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
           

翻譯過來就是說，輸入一個整數數組，該整數數組按照下标順序代表一個數字，例如[1,2,3]代表整數123，要求改變數組中元素的順序，找到比目前數字大的生成數中的最小值。如果目前數字代表的整數值已經是所有排列組合中的最大值，則傳回目前數字組成的最小值。

思路分析

如何才能找到一個值，不是過大也不是過小呢？其實，找到這幾個數字所有排列組合的可能性，然後再和目前數字一一進行比較其實也是一個思路。可是這意味着大量無用的數字的生成和比較。想要知道如何生成所有排列組合結果，可以參考我的這篇部落格

換句話說，我們要盡量用最少的比較的到最小的結果。一個數字中的各個位上的數如何調整順序才能獲得一個最小的更大值。首先，可以将低位移到高位，隻要低位的數字比高位上的數字大。但是，為了確定的到盡可能小的最大值，一定要将移動的位確定越小越好。其次，要保證移動之後，高位以後的值為最小值。

綜上所述，思路如下：

1. 由最低位（下表為nums.length-2)開始，由低往高周遊，找到可以進行替換的最小位。
2. 可以替換的條件是，比目前位低的位上存在一個數，該數比目前位上的值大，且不存在另一個比該值小且比目前位上值大的數
3. 替換數值後，該進行替換的位後序的位上的值應當保證為最小值。

例如[1，3，2]，将百位上的值和個位上的值替換以後，還要保證百位以後的值為最小值，是以最後的結果為[2,1,3]

實作代碼如下

public void nextPermutation(int[] nums) {
        for(int i = nums.length - 2 ; i>=0 ; i--){
            //尋找可以替換的最低位
            for(int j = i+1 ; j<nums.length ; j++){
                if(nums[i]<nums[j]){
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                    //確定替換位的後續位的值最小
                    Arrays.sort(nums, i+1, nums.length);
                    return;
                }
            }
            //若目前位不可替換，則自目前位開始排序，以保證下一位可以在不進行完整周遊的前提下找到最小的更大值
            Arrays.sort(nums,i,nums.length);
        }
    }
           

想要了解更多開發技術，面試教程以及網際網路公司内推，歡迎關注我的微信公衆号！将會不定期的發放福利哦~