AcWing 420. 火星人--Java
原题链接
中等
作者:
Jiang锋时刻
,
2021-02-02 14:00:40
,
所有人可见
,
阅读 301
Java 代码
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int size = sc.nextInt();
int count = sc.nextInt();
int[] arr = new int[size];
for(int i = 0; i < size; i++) {
arr[i] = sc.nextInt();
}
while(count-- > 0) {
arr = next(arr);
}
for(int i = 0; i < size; i++) {
System.out.print(arr[i] + " ");
}
}
// 下一个排列
public static int[] next(int[] arr){
int len = arr.length;
int st = 0;
int ed = 0;
for(int i = len - 2; i >= 0; i--) {
if(arr[i] < arr[i + 1]) {
st = i;
break;
}
}
for(int i = st; i < len; i++) {
if(arr[i] > arr[st]) {
ed = i;
}
}
arr = swap(arr, st, ed);
arr = reverse(arr, st + 1, len - 1);
return arr;
}
// 交换数组元素
public static int[] swap(int[] arr, int m, int n) {
int temp = arr[m];
arr[m] = arr[n];
arr[n] = temp;
return arr;
}
// 翻转数组
public static int[] reverse(int[] arr, int left, int right) {
while(left < right) {
arr = swap(arr, left, right);
left++;
right--;
}
return arr;
}
}