题解 | #牛群的编号重排# java
牛群的编号重排
https://www.nowcoder.com/practice/220a216469c14a52b4eb6709e041feb1
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[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private void reverse(int[] arr, int start, int end) { while (start < end) { swap(arr, start, end); start++; end--; } } }
编程语言:Java
该题考察的知识点:数组操作、排列、算法设计
代码的文字解释:
- 给定一个整数数组
cows
,要求计算下一个排列。 - 从数组的倒数第二个元素开始,向前遍历数组,找到第一个不满足降序的位置
i
。也就是找到第一个满足cows[i] < cows[i+1]
的i
值。 - 如果找到了满足条件的
i
,则继续从数组的末尾往前遍历,找到第一个比位置i
元素更大的元素,并将它们交换位置。 - 将位置
i+1
到末尾的部分进行反转,即将其按照升序排列。返回得到的排列数组。 - 整个过程实际上是在进行下一个排列的计算,即找到当前排列的下一个更大的排列。
其实就是一个考察基础数组排列计算的题目,有思路了代码写起来很简单