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

这道题到底在问什么

输入

num="5489355142", k=4

输出

2

输入

num="11112", k=4

输出

4

输入

num="1234", k=3

输出

2

最优解：一步一步想明白

1. 3两步套路:先用「下一个排列」做 k 次求出第 k 个最小妙数(找拐点 i、找 j 交换、反转后缀);再用冒泡把 num 逐位对齐到目标、累加相邻交换次数(等于逆序对数)。下面每帧都在套它。
2. 4先看清画面。上面这排格子是 num 等于 1234,四位数字 1、2、3、4,下标 0 到 3。任务分两步:第一步反复求「下一个排列」3 次,拿到第 3 个最小妙数当目标;第二步再数从 1234 挪到那个目标,最少要几次相邻交换。右边面板先记第一步:已经求到第几个妙数、当前排列长什么样、这一步在做什么。
3. 5求第 1 个最小妙数。从最右边往左看,找第一个「比它右邻小」的位置,这就是拐点。下标 3 是 4,它右边没有邻居;看下标 2 的 3,它右边是 4,3 小于 4,拐点就是它,i 等于 2,绿色标住。拐点意味着从这里开始往大调,能得到更大的排列。
4. 6找到拐点后,再从最右边往左找第一个「大于拐点数字 3」的位置,把它拿来和拐点换。下标 3 是 4,4 大于 3,正好,j 等于 3,蓝色标住。为什么找刚好大于它的?这样换过去,增幅最小,才是紧挨着的下一个更大排列。
5. 7把拐点 i 等于 2 的 3,和 j 等于 3 的 4 交换。1234 就变成了 1243。现在前面变大了一点,但拐点后面那一段还得处理:交换完拐点后面可能不是最小顺序,要再收拾一下。
6. 8最后把拐点后面那一段整体反转,让后缀尽量小。这次拐点在下标 2,后缀只有下标 3 一位,反转以后还是它自己,所以结果就是 1243。这就是第 1 个最小妙数。右边面板记上:已求到第 1 个。接着求第 2 个。
7. 9在 1243 上求下一个排列。还是从右往左找拐点。下标 2 是 4,它右邻是 3,4 大于 3,不是拐点,标红跳过;再看下标 1 的 2,右邻是 4,2 小于 4,拐点就是它,i 等于 1,绿色标住。
8. 10再从最右往左找第一个大于拐点数字 2 的位置。下标 3 是 3,3 大于 2,就是它,j 等于 3,蓝色标住。注意后缀 43 是递减的,从右边第一个大于 2 的必然是恰好比 2 大一点的那个,换过去增幅最小。
9. 11把拐点下标 1 的 2 和下标 3 的 3 交换,1243 变成 1342。这时拐点后面是下标 2 和 3 的 4、2,还是从大到小排的,不是最小,得反转一下才是真正的下一个排列。
10. 12把拐点后面下标 2 到 3 的 42 整体反转成 24,1342 就变成了 1324。这一步很关键:反转前是 1342,直接用会跳过好几个更小的妙数;反转后的 1324 才是紧挨着 1243 的下一个。已求到第 2 个,再求第 3 个。
11. 13在 1324 上求最后一次下一排列。从右往左找拐点:下标 2 是 2,右邻下标 3 是 4,2 小于 4,拐点立刻就是它,i 等于 2,绿色标住。这次拐点靠得很右,后面处理会很轻。
12. 14从最右往左找第一个大于拐点数字 2 的位置。下标 3 是 4,4 大于 2,就是它,j 等于 3,蓝色标住。拐点后面只有这一位,待会儿交换完基本就成了。
13. 15把拐点下标 2 的 2 和下标 3 的 4 交换,1324 变成 1342。拐点后面只剩一位,反转它还是自己,所以直接就是结果。第 3 个最小妙数就是 1342,这正是我们要够到的目标串。第一步大功告成。
14. 16第二步换个目标记法。上面重新摆回原串 1234,右边面板改记第二步:目标串是 1342,已经对齐的前缀、以及累计交换了几次。规则是每次只能交换相邻两位。我们从左到右,一位一位把当前串对齐成目标,顺手把交换次数加起来。
15. 17看目标第 0 位,要的是 1。当前串下标 0 正好就是 1,不用动,零次交换。绿色标住下标 0,它已经对齐好了。前缀「1」锁定,往后这一位不再碰。看第 1 位。
16. 18目标第 1 位要的是 3。在当前串 1234 里,3 待在下标 2,可它该去下标 1。绿色标住这个 3,红色标下标 1,那是它的目的地。相邻交换只能一步步挪,所以要把 3 和它左边的 2 交换,往左顶一格。
17. 19交换下标 1 和 2 的 2 和 3,当前串从 1234 变成 1324。3 顺利落到下标 1,和目标对上了。交换次数从 0 加到 1。绿色标住就位的 3。现在前缀「13」都对齐了,看第 2 位。
18. 20目标第 2 位要的是 4。当前串 1324 里,4 待在下标 3,它该去下标 2。绿色标住这个 4,红色标下标 2 是目的地。同样用相邻交换,把 4 和它左边的 2 换一下,往左顶一格。
19. 21交换下标 2 和 3 的 2 和 4,当前串从 1324 变成 1342。4 落到下标 2,对上目标。交换次数从 1 加到 2。绿色标住就位的 4。此时前缀「134」都对齐了,只剩最后一位。
20. 22看目标最后一位,要的是 2。当前串 1342 的下标 3 已经是 2,自动就位,不用再换。绿色标住它。到这里当前串已经完全等于目标串 1342,交换次数停在 2。为什么最后一位总能自动对上?前三位都对齐了,剩下的那位没得选,一定也对。
21. 23收尾。当前串已经完全变成目标 1342,一路数下来:对齐 3 用了 1 次交换,对齐 4 又用了 1 次,一共 2 次。这就是把 1234 变成第 3 个最小妙数所需的最少相邻交换次数。整个过程分两步:先用下一个排列求出目标,再用冒泡对齐数出代价。
22. 24再从另一个角度复核一遍。目标串 1342 的每一位,分别来自原串的下标 0、2、3、1。把这串下标 0、2、3、1 看成一个排列,数它有几对「前面的比后面的大」的逆序对:2 比 1 大是一对,3 比 1 大又是一对,一共 2 对。逆序对数恰好等于相邻交换的最小次数,这也是参考代码直接数逆序对的道理。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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))

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问