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

import java.util.*;


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

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void reverse(int[] nums, int i, int j) {
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
}

Java代码

该题考察的是下一个排列的算法。给定一个整数数组，要求找到比当前排列大的下一个排列。如果不存在比当前排列大的下一个排列，则返回将数组按升序排序后的结果。

代码的文字解释如下：

首先，定义一个指针i，并初始化为数组长度-2。
从数组的倒数第二个元素开始，向前遍历，找到第一个满足nums[i] < nums[i + 1]的元素，记为i。
如果存在i >= 0，说明可以找到一个比当前排列大的下一个排列。继续从数组的最后一个元素向前遍历，找到第一个大于nums[i]的元素，记为j。交换nums[i]与nums[j]。
反转数组中i + 1到最后一个元素之间的所有元素，使得这部分元素按照升序排列。
返回得到的下一个排列。