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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param cows int整型一维数组
     * @return int整型一维数组
     */
   public int[] nextPermutation (int[] cows) {
        // 找到第一个降序的位置，从右往左
        int index = cows.length-2;
        while (index>=0 && cows[index]<=cows[index+1]){
            index--;
        }

        //如果找到了，说明不是最大的排列，需要交换
        if(index>=0) {
            //找到右边比cows[index]大的最小的数，从右往左
            int j = cows.length - 1;
            while (j > index && cows[j] > cows[index]) {
                j--;
            }
            // 交换cows[i]和cows[j]
            swap(cows,index,j);
        }
        // 反正cows[i+1]到cows[length-1]之间的元素，使其升序
        reverse(cows,index+1,cows.length-1);
        return cows;
    }

    public void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public void reverse(int[] cows,int start,int end){
        while (start<end){
            swap(cows,start,end);
            start++;
            end--;
        }
    }
}

本题考察的知识点是数组元素交换，所用编程语言是java。

这个问题可以分为以下几个步骤：

1.从右往左找到第一个升序的位置 i ，即 cows[i] > cows[i+1] 。这个位置 i 之后的元素都是升序的，所以它们已经是最小的排列，不能再变小了。

2.如果 i 存在，说明数组 cows 不是最小的排列，还有可能变小。那么我们需要在 i 之后的元素中找到一个比 cows[i] 小的最小的数 j ，即 cows[j] <cows[i] ，并且 j 是满足这个条件的最右边的位置。这样，我们把 cows[i] 和 cows[j] 交换，就可以让数组 cows 变得更小一点。

3.交换后，i 之后的元素仍然是升序的，但是我们想要找到下一个排列，也就是比当前排列稍微小一点的排列。所以我们需要把 i 之后的元素反转，使它们变成降序的，这样就可以得到下一个排列了。

4.如果 i 不存在，说明数组 cows 已经是最大的排列，没有下一个排列了。那么我们需要把数组 cows 反转，使它变成最小的排列，也就是升序的。