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

import java.util.*;


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

考察的知识点：

1. 数组遍历和操作：对数组进行遍历、交换、翻转等操作。
2. 数组的字典序和排列问题：理解如何找到下一个更大的排列。
3. 原地修改和常数空间：题目要求在原数组上修改且使用常数空间。

解题思路:

以1，5，2，3，7举例。

1.从右到左找到非递减的数，5，如果没有找到直接就进入了步骤3

2.从5开始从左到右找到非递增的数，7。交换5和7之前的数3，此时数组为1，3，2，5，7。

3.反正3之后的数组，结果数组为1，3，7，5，2.