AcWing 420. 下一个排列,Java解法
原题链接
中等
作者:
zlnnjit
,
2021-02-07 23:12:06
,
所有人可见
,
阅读 294
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = sc.nextInt();
while (m-- > 0) {
int k = n - 1;
while (arr[k - 1] > arr[k]) k--;
//此时第一个升序的位置就是k-1,最大降序的位置是k
int t = k;
while (t + 1 < n && arr[t + 1] > arr[k - 1]) t++;
//此时t为最小比k-1大的数,然后互换t和k-1的位置
int tmp = arr[t]; arr[t] = arr[k - 1]; arr[k - 1] = tmp;
//然后调换降序序列为升序序列 这里需要注意排序的范围为[k,n-1],不包含n
Arrays.sort(arr, k, n);
}
for (int i = 0; i < n; i++) System.out.print(arr[i] + " ");
}
}