LeetCode 31 Next Permutation(次の配列)

翻訳

  “     ”  ，                         。

              ，               （     ）。

       ，        。

       ，     ，     ：

1，2，3 → 1，3，2
3，2，1 → 1，2，3
1，1，5 → 1，5，1

テキスト

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」の全配列は、次のようになっています.

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

だから、上の行から次の行に並び替え、最後の行になったら最初の行に並び替えるという意味です.
ただし、追加のスペースを消費できないため、与えられた配列の数に基づいてすべての配列をリストすることはできません.
ぶんせき
ネット上では一つの例を見て、いいと思います.もう一つ探す必要はありません.

6 5 4 8 7 5 1

最初は相手の后ろの绍介を见ていないで、自分でこの并びの次の并びがどんなものかを考えています.

          ，1 5      。

7、5 1        ，      8、7、5、1    。

           ，          。

               。

     4，    4   5   8  7   1。

        4             ，       。

         ：6 5 5 8 7 4 1

          8 7 4 1     。

コード#コード#
上記の考え方に基づいて、手帳には次のようなコードが一気に書かれています.

class Solution {
       
public:
    void nextPermutation(vector<int>& nums) {
        int index = nums.size() - 1;
        while(nums[index] < nums[index-1]) {
            --index;
        }
        if(index == 0) {
            sort(nums.begin(), nums.end());
            return ;
        }

        int second = INT_MAX, secondIndex = INT_MAX;
        for(int i = nums.size() - 1; i >= index - 1; -- i) {
            if(nums[i] > nums[index - 1]) {
                if(nums[i] < second) {
                    second = nums[i];
                    secondIndex = i;
                }               
            }               
        }       
        int temp = nums[index - 1];
        nums[index - 1] = nums[secondIndex];
        nums[secondIndex] = temp;

        sort(nums.begin()+index, nums.end());       
    }
}

LeetCodeに提出して、間違っていることに気づきました・・・最後の行に1つのセミコロンが欠けていて、加えても間違っていました・・・
仕方なく素直にCodeBlocksでデバッグして、記号を付けて正解(以下の=):

while(nums[index] <= nums[index-1]) {
            --index;
}

そこで次に他の人の解法を見てみると、次の3つの違いがあります.

while(index > 0){
   if(num[index] > num[index - 1]){
       break;
   }
   index--;
}

int exchangeIndex;
for(int i = num.size()-1; i >= index; i--){
   if(num[i] > num[index-1]){
       exchangeIndex = i;
       break;
   }
}

swap(num[index-1],num[exchangeIndex]);

whileサイクルという部分はもっと簡単ですが、他はもっと複雑で、swapは思いもよらなかった......
拡張
C++標準ライブラリにもう一つの関数next_permutationは、1つの数値シーケンスを求めるための次のソートです.

void nextPermutation(vector<int> &num) {  
    next_permutation( num.begin(), num.end() );  
}  

もっと頑張れ...