题解 | #牛群的编号重排#

知识点：数组，双指针

该题目难点在于理解，我们如何找到下一个字典序更小的排列，首先我们需要知道，下一个字典序更小的数字是什么，如何才能让一个数字的排列更小。

对于1，2，3来说，字典序的排列为：

1，2，3

1，3，2

2，1，3

2，3，1

3，1，2

3，2，1

我们要做的是找到一个小于当前序列的新序列，并且，新序列的变化程度要尽可能地小。很容易想到的是，我们要找一个较大的值，和右侧更小的一个值进行交换，这样才能让序列变小。对于较大的值 i 来说，我们从后往前找出第一个大于后方数字的值作为较大值 i，然后在右方找出小于 i 的值，作为较小的值 j，将二者进行交换，交换完之后，i 位置右边的数需要重新排序，这样可以在保证新排列小于原来排列的情况下，使变小的幅度尽可能小。

Java题解如下

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cows int整型一维数组 
     * @return int整型一维数组
     */
    public int[] nextPermutation (int[] cows) {
        // write code here
        int index = cows.length - 2;
        while(index >= 0 && cows[index] <= cows[index + 1]) {
            index--;
        }
        if(index >= 0) {
            int j = cows.length - 1;
            while(j >= 0 && cows[index] <= cows[j]) {
                j--;
            }
            swap(cows, index, j);
        }
        reverse(cows, index + 1);
        return cows;
    }

    private void reverse(int[] cows, int index) {
        int left = index, right = cows.length - 1;
        while(left < right) {
            swap(cows, left, right);
            left++;
            right--;
        }
    }

    private void swap(int[] cows, int i, int j) {
        if(i == j) {
            return;
        }
        cows[i] ^= cows[j];
        cows[j] ^= cows[i];
        cows[i] ^= cows[j];
    }
}