Java 编程实现排列交换判断

使用 Java 编程判断排列交换

小红有一个长度为 n 的排列，她可以选择两个位置，然后交换两个位置的数。她想知道能否通过最多一次交换，使得存在一个连续子段，是长度为 k 的排列。

排列是指一个长度为 len 的整数数组，数组中包含 1 到 len 的每个数，且每个数只出现一次。

输入描述 一行两个整数 n，k，表示排列长度和连续子段长度。一行 n 个整数 a1, a2, ..., an，表示排列。 1 ≤ k ≤ n ≤ 10^5

输出描述 如果能够通过最多一次交换，存在一个连续子段是排列，输出 YES，并输出交换的位置: 先输出一个整数 x (0 ≤ x ≤ 1)，然后输出 x 行，每行两个整数 u，v，表示交换位置 uv。否则输出 NO。

思路：

首先判断原始排列是否已经是一个连续子段，如果是，则输出 YES 并且不需要交换位置；
如果不是连续子段，则遍历整个排列，找到第一个不在正确位置上的数，记为 num；
从 num 开始向后找连续子段，直到找到长度为 k 的连续子段或者遍历完整个排列；
如果找到了长度为 k 的连续子段，输出 YES，并输出交换的位置为 num 和子段的第一个数；
如果没有找到长度为 k 的连续子段，输出 NO。

代码实现如下：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        sc.close();
        
        // 判断是否已经是连续子段
        boolean isConsecutive = true;
        for (int i = 0; i < n; i++) {
            if (arr[i] != i + 1) {
                isConsecutive = false;
                break;
            }
        }
        
        if (isConsecutive) {
            System.out.println("YES");
            System.out.println("0");
        } else {
            // 找到第一个不在正确位置上的数
            int num = 0;
            for (int i = 0; i < n; i++) {
                if (arr[i] != i + 1) {
                    num = arr[i];
                    break;
                }
            }
            
            // 从 num 开始找连续子段
            int start = 0;
            int end = 0;
            for (int i = 0; i < n; i++) {
                if (arr[i] == num) {
                    start = i;
                    end = i + 1;
                    while (end < n && arr[end] == arr[end - 1] + 1) {
                        end++;
                    }
                    break;
                }
            }
            
            // 判断是否找到了长度为 k 的连续子段
            if (end - start == k) {
                System.out.println("YES");
                System.out.println("1");
                System.out.println((start + 1) + " " + (end + 1));
            } else {
                System.out.println("NO");
            }
        }
    }
}