最小排列

#include <bits/stdc++.h>
using namespace std;

int a[100001], b[100001];
int main(){
    int n, x;
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        scanf("%d", &a[i]);
        b[a[i]] = i;
    }
    for(int i=1;i<=n;i++){
        if(a[i]!=i){
            x = b[i];
            a[x] = a[i];
            a[i] = i;
            for(int i=1;i<=n;i++){
                if(i==n)
                    printf("%d\n", a[i]);
                else
                    printf("%d ", a[i]);
            }
            return 0;
        }
    }
    a[n] = n-1;
    a[n-1] = n;
    for(int i=1;i<=n;i++){
        if(i==n)
            printf("%d\n", a[i]);
        else
            printf("%d ", a[i]);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;++i) cin>>v[i];
    int j = -1;
    // 递增的部分直接先跳过
    for(int i=1;i<n;++i){
        if(v[i]>=v[i-1]) continue;
        else{
            j = i;
            break;
        }
    }
    // 整个序列都单调递增 交换最后两个数
    if(j==-1){
        int tmp = v[n-1];
        v[n-1] = v[n-2];
        v[n-2] = tmp;
    }else{
        // 否则从不单调的位置开始往后找一个最小值
        // 从头扫描一个比该值大的位置进行交换
        int MIN = INT_MAX;
        int idx = -1;
        for(int k=j;k<n;++k){
            if(v[k]<MIN){
                idx = k;
                MIN = v[k];
            }
        }
        for(int i=0;i<n;++i){
            if(v[i]>MIN){
                int t = v[i];
                v[i] = MIN;
                v[idx]=t;
                break;
            }
        }
    }
    for(auto t:v)
        cout<<t<<" ";

    return 0;
}

# 寻找差最大的一对逆序，记录对应的索引，交换对应元素，输出新序列
# 思路有问题，并不是找逆序，而是尽量保证靠前的数字按顺序排列，越靠前优先级越高
# 如果顺序都正确，交换最后两个数字，因为必须组一次交换（题目要求）
n = int(input())
ln = list(map(int, input().split()))
for i in range(len(ln)):
    if ln[i] != i+1:
        for j in range(i+1, len(ln)):
            if ln[j] == i+1:
                ln[i], ln[j] = ln[j], ln[i]
                break  # 这个不是必要的，但是提前截断循环，节约时间
        break  # 操作且只操作一次
else:   # 所有元素顺序都正确
    ln[-1], ln[-2] = ln[-2], ln[-1]
print(" ".join((map(str, ln))))

//1-n有序排列，找出第一个不在原位置的数，找出最小的不在原位置的数，交换这两个数即可
//注意给出的数组若是有序也要交换，此时交换最后两个数即可
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        while(scan.hasNext()) {
            int n = scan.nextInt();
            int[]data=new int[n+1];
            for(int i=1;i<n+1;i++){
                data[i]=scan.nextInt();
            }
            boolean flag=false;
            int firstpoi=1;
            int minpoi=0;
            int min=Integer.MAX_VALUE;
            for(int i=1;i<n+1;i++){
                if(data[i]!=i){
                    if(flag==false){
                        firstpoi=i;
                        flag=true;
                    }
                    if(min>data[i]){
                        minpoi=i;
                        min=data[i];
                    }
                }
            }
            if(flag==true){
                data[minpoi]=data[firstpoi];
                data[firstpoi]=min;
            }else{
                int tem=data[n];
                data[n]=data[n-1];
                data[n-1]=tem;
            }
            System.out.print(data[1]);
            for(int i=2;i<n+1;i++){
                System.out.print(" "+data[i]);
            }
        }
    }
}

	

package main

import (
    "fmt"
    "os"
    "bufio"
)

var in=bufio.NewReader(os.Stdin)

func main() {
    var n int
    fmt.Scan(&n)
    arr:=make([]int,n)
    pre,cur:=-1,-1
    for i:=0;i<n;i++{
        fmt.Fscan(in,&arr[i])
        if pre==-1{
            if arr[i]!=i+1{
                pre=i
            }
        }else{
            if arr[i]==pre+1{
                cur=i
            }
        }
    }
    if pre==-1{
        arr[n-2],arr[n-1]=arr[n-1],arr[n-2]
    }else{
        arr[pre],arr[cur]=arr[cur],arr[pre]
    }
    for _,x:=range arr{
        fmt.Printf("%v ",x)
    }
}

n, a = int(input()), list(map(int, input().split()))
for i in range(n):
    if a[i] != i + 1:
        a[a.index(i + 1)], a[i] = a[i], i + 1
        break
    if i == n - 1: a[i - 1], a[i] = a[i], a[i - 1]
print(' '.join(map(str, a)))

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int N;
    cin>>N;
    vector<int> rec(N);
    for(int i=0;i<N;i++)
    {
        cin>>rec[i];
    }
    if(is_sorted(rec.begin(),rec.end()))
    {
        for(int i=0;i<N-2;i++)
        {
            cout<<rec[i]<<' ';
        }
        cout<<*(rec.end()-1)<<' '<<*(rec.end()-2)<<endl;
    }
    else
    {
    vector<int> orin;
    copy(rec.begin(),rec.end(),inserter(orin,orin.begin()));
    sort(rec.begin(),rec.end());
    for(int i=0;i<N;i++)
    {
        if(rec[i]!=orin[i])
        {
            auto flag=find(orin.begin(),orin.end(),rec[i]);
            *flag=orin[i];
            orin[i]=rec[i];
            break;
        }
    }
    for(auto s:orin)
    {
        cout<<s<<' ';
    }
    }
}

如果给出的序列本身就是最小序列，也就是1,2,3……n-1，n
由于题目说必须要进行一次交换，所以只能交换n-1 和 n

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }
        solve(n, a);
        for (int i = 1; i <= n - 1; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println(a[n]);
    }
    private static void solve(int n, int[] a) {
        for (int i = 1; i <= n; i++) {
            if (a[i] == i) {
                continue;
            }
            for (int j = i + 1; j <= n; j++) {
                if (a[j] == i) {
                    a[j] = a[i];
                    a[i] = i;
                    return;
                }
            }
        }
        a[n] = n - 1;
        a[n - 1] = n;
    }
}