邻位交换的最小次数 图解题解

妙数是什么，这道题的两步分别求什么

给一个用字符串表示的大整数 num 和整数 k。把 num 各位数字重排，只要排出的数值比 num 大，就算一个「妙数」；妙数很多，只关心最小的几个。分两步：先找第 k 个最小妙数当目标串，再算把 num 变成它、每次只能换相邻两位、最少换几次。题面 num 为 1234、k 取 3 时，第 3 个最小妙数是 1342，答案 2 次。

把全部排列列出来挑第 k 个，为什么走不通

n 位数字全排列有 n! 种，全摊开挑比 num 大的、排序取第 k 个，n 才到 10 就三百多万种，二十位是天文数字，列不完。既然只要紧挨 num 往上的第 k 个，就该能从 num 一步步跳到下一个更大排列，不必铺开全部。

下一个排列怎么求，交换次数又凭什么等于逆序对

第一步靠「下一个排列」：求出比当前大、又是更大排列里最小的那个，即字典序上紧挨着的后一个。三步——从右往左找第一个比右邻小的位置叫拐点；再从右往左找第一个比拐点大的位置，两者交换；把拐点后的后缀反转成升序。从 num 连做 k 次，依次得第 1 到第 k 个最小妙数。

第二步只能换相邻两位。把目标每一位来自原串的哪个下标排成一串——逆序对，指这串里前面的数比后面的大的一对。一次相邻交换只调换相邻两个、至多消掉一个逆序对，所以最少次数正好等于这串下标的逆序对数。数字有重复时，相同数字要按原串里的先后去对应，才不会多造逆序对。

1234 连做三次下一个排列，怎样逼出 1342

从 1234 求第 1 个：拐点是下标 2 的 3，从右找第一个比 3 大的即下标 3 的 4，交换得 1243，后缀一位反转不变。在 1243 求第 2 个：拐点退到下标 1 的 2，和下标 3 的 3 交换得 1342，后缀 42 是降序，反转成 24 才得 1324——这步别省，不反转就跳过 1324。在 1324 求第 3 个：拐点是下标 2 的 2，和下标 3 的 4 交换得 1342，后缀不变即目标。

把 1234 挪成 1342，两次交换是怎么数出来的

目标 1342 的四位分别来自原串 1234 的下标 0、2、3、1。逐位对齐：第 0 位要 1，下标 0 已是 1；第 1 位要 3，3 在下标 2，换到下标 1，串变 1324，计 1 次；第 2 位要 4，4 在下标 3，换到下标 2，串变 1342，计 2 次；第 3 位要 2 已就位，共 2 次。换个角度数下标串 0、2、3、1 的逆序对：2 比 1、3 比 1 各一对，也是 2。

后缀忘反转、重复数字乱配，答案就跟着错

复杂度上，第一步 k 次下一个排列各扫一遍，是 O(k·n)；第二步双重循环数逆序对，是 O(n²)，合计 O(k·n+n²)。逆序对换树状数组可降到 O(n log n)。额外只有下标桶和位置数组，空间 O(n)。

下一个排列最阴的是反转后缀：交换完拐点直接用，会跳过更小的妙数、第 k 个整串错位。有重复也藏坑——像 11112 求第 4 个得 21111、答案 4，那几个 1 得按原串先后对应，乱配就多造逆序对。还有别混：数的是相邻交换、等于逆序对数，任意位置能换几步就排好，那是另一道题。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def getMinSwaps(self, num: str, k: int) -> int:
        def next_permutation(nums: List[str]) -> bool:
            n = len(nums)
            i = n - 2
            while i >= 0 and nums[i] >= nums[i + 1]:
                i -= 1
            if i < 0:
                return False
            j = n - 1
            while j >= 0 and nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
            nums[i + 1 : n] = nums[i + 1 : n][::-1]
            return True

        s = list(num)
        for _ in range(k):
            next_permutation(s)
        d = [[] for _ in range(10)]
        idx = [0] * 10
        n = len(s)
        for i, c in enumerate(num):
            j = ord(c) - ord("0")
            d[j].append(i)
        arr = [0] * n
        for i, c in enumerate(s):
            j = ord(c) - ord("0")
            arr[i] = d[j][idx[j]]
            idx[j] += 1
        return sum(arr[j] > arr[i] for i in range(n) for j in range(i))

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int getMinSwaps(string num, int k) {
        string s = num;
        for (int i = 0; i < k; ++i) {
            next_permutation(begin(s), end(s));
        }
        vector<int> d[10];
        int n = num.size();
        for (int i = 0; i < n; ++i) {
            d[num[i] - '0'].push_back(i);
        }
        int idx[10]{};
        vector<int> arr(n);
        for (int i = 0; i < n; ++i) {
            arr[i] = d[s[i] - '0'][idx[s[i] - '0']++];
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (arr[j] > arr[i]) {
                    ++ans;
                }
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int getMinSwaps(String num, int k) {
        char[] s = num.toCharArray();
        for (int i = 0; i < k; ++i) {
            nextPermutation(s);
        }
        List<Integer>[] d = new List[10];
        Arrays.setAll(d, i -> new ArrayList<>());
        int n = s.length;
        for (int i = 0; i < n; ++i) {
            d[num.charAt(i) - '0'].add(i);
        }
        int[] idx = new int[10];
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = d[s[i] - '0'].get(idx[s[i] - '0']++);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (arr[j] > arr[i]) {
                    ++ans;
                }
            }
        }
        return ans;
    }

    private boolean nextPermutation(char[] nums) {
        int n = nums.length;
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            --i;
        }
        if (i < 0) {
            return false;
        }
        int j = n - 1;
        while (j >= 0 && nums[i] >= nums[j]) {
            --j;
        }
        swap(nums, i++, j);
        for (j = n - 1; i < j; ++i, --j) {
            swap(nums, i, j);
        }
        return true;
    }

    private void swap(char[] nums, int i, int j) {
        char t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}