Medium

题目描述

给你一个字符串 num，表示一个大整数，以及一个整数 k。

如果某个整数是 num 中数字的一个排列且大于 num 的值，我们就称这个整数是美妙的。可能有很多美妙的整数，但我们只关心其中最小的几个。

例如，当 num = "5489355142" 时：

  • 第 1 个最小的美妙整数是 "5489355214"
  • 第 2 个最小的美妙整数是 "5489355241"
  • 第 3 个最小的美妙整数是 "5489355412"
  • 第 4 个最小的美妙整数是 "5489355421"

返回需要对 num 进行的最小相邻数字交换次数，以到达第 k 个最小的美妙整数。

题目保证第 k 个最小的美妙整数存在。

示例 1：

输入：num = "5489355142", k = 4
输出：2
解释：第 4 个最小的美妙数是 "5489355421"。要得到这个数：
- 交换索引 7 和索引 8："5489355142" -> "5489355412"
- 交换索引 8 和索引 9："5489355412" -> "5489355421"

示例 2：

输入：num = "11112", k = 4
输出：4
解释：第 4 个最小的美妙数是 "21111"。要得到这个数：
- 交换索引 3 和索引 4："11112" -> "11121"
- 交换索引 2 和索引 3："11121" -> "11211"
- 交换索引 1 和索引 2："11211" -> "12111"
- 交换索引 0 和索引 1："12111" -> "21111"

示例 3：

输入：num = "00123", k = 1
输出：1
解释：第 1 个最小的美妙数是 "00132"。要得到这个数：
- 交换索引 3 和索引 4："00123" -> "00132"

约束条件：

  • 2 <= num.length <= 1000
  • 1 <= k <= 1000
  • num 仅由数字组成

解题思路

这道题可以分为两个步骤：

  1. 找到第 k 个最小的美妙数：通过 k 次调用下一个排列（next permutation）算法来获得目标字符串。下一个排列算法是经典的字典序算法，步骤为：从右往左找第一个递减的位置，然后找到右侧最小的大于该位置的数字进行交换，最后将右侧部分反转。

  2. 计算最小交换次数：得到目标字符串后，需要计算从原字符串变换到目标字符串的最小相邻交换次数。这里使用贪心策略：对于目标字符串的每一位，在当前字符串中找到对应的字符，然后通过相邻交换将其移动到正确位置。

具体实现时，我们维护当前字符串的状态，对于目标字符串的每个位置，找到当前字符串中第一个匹配的字符（从左到右），然后通过冒泡排序的方式将其移动到目标位置，记录交换次数。

时间复杂度主要由两部分组成：k 次下一个排列操作和计算交换次数。整体算法是高效的贪心解法。

代码实现

class Solution {
public:
    int getMinSwaps(string num, int k) {
        string target = num;
        
        // 找到第k个下一个排列
        for (int i = 0; i < k; i++) {
            nextPermutation(target);
        }
        
        // 计算最小交换次数
        vector<char> current(num.begin(), num.end());
        int swaps = 0;
        
        for (int i = 0; i < target.length(); i++) {
            if (current[i] != target[i]) {
                // 找到需要交换的位置
                int j = i + 1;
                while (current[j] != target[i]) {
                    j++;
                }
                
                // 通过相邻交换将current[j]移动到位置i
                while (j > i) {
                    swap(current[j], current[j-1]);
                    j--;
                    swaps++;
                }
            }
        }
        
        return swaps;
    }
    
private:
    void nextPermutation(string& nums) {
        int n = nums.length();
        int i = n - 2;
        
        // 找到第一个递减的位置
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        
        if (i >= 0) {
            // 找到右侧最小的大于nums[i]的数
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            swap(nums[i], nums[j]);
        }
        
        // 反转右侧部分
        reverse(nums.begin() + i + 1, nums.end());
    }
};

class Solution:
    def getMinSwaps(self, num: str, k: int) -> int:
        target = list(num)
        
        # 找到第k个下一个排列
        for _ in range(k):
            self.next_permutation(target)
        
        # 计算最小交换次数
        current = list(num)
        swaps = 0
        
        for i in range(len(target)):
            if current[i] != target[i]:
                # 找到需要交换的位置
                j = i + 1
                while current[j] != target[i]:
                    j += 1
                
                # 通过相邻交换将current[j]移动到位置i
                while j > i:
                    current[j], current[j-1] = current[j-1], current[j]
                    j -= 1
                    swaps += 1
        
        return swaps
    
    def next_permutation(self, nums):
        n = len(nums)
        i = n - 2
        
        # 找到第一个递减的位置
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        
        if i >= 0:
            # 找到右侧最小的大于nums[i]的数
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        
        # 反转右侧部分
        nums[i + 1:] = reversed(nums[i + 1:])

public class Solution {
    public int GetMinSwaps(string num, int k) {
        char[] target = num.ToCharArray();
        
        // 找到第k个下一个排列
        for (int i = 0; i < k; i++) {
            NextPermutation(target);
        }
        
        // 计算最小交换次数
        char[] current = num.ToCharArray();
        int swaps = 0;
        
        for (int i = 0; i < target.Length; i++) {
            if (current[i] != target[i]) {
                // 找到需要交换的位置
                int j = i + 1;
                while (current[j] != target[i]) {
                    j++;
                }
                
                // 通过相邻交换将current[j]移动到位置i
                while (j > i) {
                    char temp = current[j];
                    current[j] = current[j-1];
                    current[j-1] = temp;
                    j--;
                    swaps++;
                }
            }
        }
        
        return swaps;
    }
    
    private void NextPermutation(char[] nums) {
        int n = nums.Length;
        int i = n - 2;
        
        // 找到第一个递减的位置
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        
        if (i >= 0) {
            // 找到右侧最小的大于nums[i]的数
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            char temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        
        // 反转右侧部分
        Array.Reverse(nums, i + 1, n - i - 1);
    }
}

var getMinSwaps = function(num, k) {
    let target = num.split('');
    
    // 找到第k个下一个排列
    for (let i = 0; i < k; i++) {
        nextPermutation(target);
    }
    
    // 计算最小交换次数
    let current = num.split('');
    let swaps = 0;
    
    for (let i = 0; i < target.length; i++) {
        if (current[i] !== target[i]) {
            // 找到需要交换的位置
            let j = i + 1;
            while (current[j] !== target[i]) {
                j++;
            }
            
            // 通过相邻交换将current[j]移动到位置i
            while (j > i) {
                [current[j], current[j-1]] = [current[j-1], current[j]];
                j--;
                swaps++;
            }
        }
    }
    
    return swaps;
};

function nextPermutation(nums) {
    let n = nums.length;
    let i = n - 2;
    
    // 找到第一个递减的位置
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    
    if (i >= 0) {
        // 找到右侧最小的大于nums[i]的数
        let j = n - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    
    // 反转右侧部分
    reverse(nums, i + 1, n - 1);
}

function reverse(nums, start, end) {
    while (start < end) {
        [nums[start], nums[end]] = [nums[end], nums[start]];
        start++;
        end--;
    }
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(k × n + n²)k次下一个排列操作，每次O(n)；计算交换次数最坏O(n²)
空间复杂度O(n)存储目标字符串和当前字符串

相关题目