Medium

题目描述

给你一个由不同正整数组成的数组 nums。你需要根据每个数字的数位和按升序对数组进行排序。如果两个数字具有相同的数位和，则较小的数字应在排序后的顺序中排在前面。

返回将 nums 重新排列为这种排序顺序所需的最小交换次数。

交换定义为交换数组中两个不同位置的值。

示例 1：

输入：nums = [37,100]
输出：1
解释：
计算每个整数的数位和：[3 + 7 = 10, 1 + 0 + 0 = 1] → [10, 1]
根据数位和排序整数：[100, 37]。交换 37 和 100 得到排序顺序。
因此，重新排列 nums 所需的最小交换次数是 1。

示例 2：

输入：nums = [22,14,33,7]
输出：0
解释：
计算每个整数的数位和：[2 + 2 = 4, 1 + 4 = 5, 3 + 3 = 6, 7 = 7] → [4, 5, 6, 7]
根据数位和排序整数：[22, 14, 33, 7]。数组已经排序。
因此，重新排列 nums 所需的最小交换次数是 0。

示例 3：

输入：nums = [18,43,34,16]
输出：2
解释：
计算每个整数的数位和：[1 + 8 = 9, 4 + 3 = 7, 3 + 4 = 7, 1 + 6 = 7] → [9, 7, 7, 7]
根据数位和排序整数：[16, 34, 43, 18]。交换 18 和 16，交换 43 和 34 得到排序顺序。
因此，重新排列 nums 所需的最小交换次数是 2。

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • nums 由不同的正整数组成

解题思路

这道题可以分为两个步骤：排序和计算最小交换次数。

第一步：确定目标排序顺序

  • 计算每个数字的数位和
  • 按数位和升序排序，如果数位和相同则按数值升序排序

第二步：计算最小交换次数 关键观察：这个问题本质上是求将一个排列变成目标排列的最小交换次数。我们可以将原数组中的每个元素映射到它在目标排序中应该出现的位置，这样就得到了一个位置映射数组。

最小交换次数 = n - 循环数量

其中循环是指置换中的环。例如，如果位置0的元素应该在位置2，位置2的元素应该在位置1，位置1的元素应该在位置0，这就形成了一个长度为3的循环。

算法流程：

  1. 计算每个数字的数位和
  2. 创建排序后的数组
  3. 建立从原数值到目标位置的映射
  4. 通过DFS或并查集找到所有循环
  5. 返回 n - 循环数量

代码实现

class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int n = nums.size();
        
        // 计算数位和
        auto digitSum = [](int x) {
            int sum = 0;
            while (x > 0) {
                sum += x % 10;
                x /= 10;
            }
            return sum;
        };
        
        // 创建排序数组
        vector<int> sorted_nums = nums;
        sort(sorted_nums.begin(), sorted_nums.end(), [&](int a, int b) {
            int sumA = digitSum(a), sumB = digitSum(b);
            if (sumA != sumB) return sumA < sumB;
            return a < b;
        });
        
        // 建立数值到目标位置的映射
        unordered_map<int, int> pos_map;
        for (int i = 0; i < n; i++) {
            pos_map[sorted_nums[i]] = i;
        }
        
        // 计算循环数量
        vector<bool> visited(n, false);
        int cycles = 0;
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                cycles++;
                int curr = i;
                while (!visited[curr]) {
                    visited[curr] = true;
                    curr = pos_map[nums[curr]];
                }
            }
        }
        
        return n - cycles;
    }
};

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 计算数位和
        def digit_sum(x):
            return sum(int(d) for d in str(x))
        
        # 创建排序数组
        sorted_nums = sorted(nums, key=lambda x: (digit_sum(x), x))
        
        # 建立数值到目标位置的映射
        pos_map = {num: i for i, num in enumerate(sorted_nums)}
        
        # 计算循环数量
        visited = [False] * n
        cycles = 0
        
        for i in range(n):
            if not visited[i]:
                cycles += 1
                curr = i
                while not visited[curr]:
                    visited[curr] = True
                    curr = pos_map[nums[curr]]
        
        return n - cycles

public class Solution {
    public int MinSwaps(int[] nums) {
        int n = nums.Length;
        
        // 计算数位和
        int DigitSum(int x) {
            int sum = 0;
            while (x > 0) {
                sum += x % 10;
                x /= 10;
            }
            return sum;
        }
        
        // 创建排序数组
        var sortedNums = nums.OrderBy(x => DigitSum(x)).ThenBy(x => x).ToArray();
        
        // 建立数值到目标位置的映射
        var posMap = new Dictionary<int, int>();
        for (int i = 0; i < n; i++) {
            posMap[sortedNums[i]] = i;
        }
        
        // 计算循环数量
        var visited = new bool[n];
        int cycles = 0;
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                cycles++;
                int curr = i;
                while (!visited[curr]) {
                    visited[curr] = true;
                    curr = posMap[nums[curr]];
                }
            }
        }
        
        return n - cycles;
    }
}

var minSwaps = function(nums) {
    const n = nums.length;
    
    // 计算数位和
    const digitSum = (x) => {
        let sum = 0;
        while (x > 0) {
            sum += x % 10;
            x = Math.floor(x / 10);
        }
        return sum;
    };
    
    // 创建排序数组
    const sortedNums = [...nums].sort((a, b) => {
        const sumA = digitSum(a), sumB = digitSum(b);
        if (sumA !== sumB) return sumA - sumB;
        return a - b;
    });
    
    // 建立数值到目标位置的映射
    const posMap = new Map();
    for (let i = 0; i < n; i++) {
        posMap.set(sortedNums[i], i);
    }
    
    // 计算循环数量
    const visited = new Array(n).fill(false);
    let cycles = 0;
    
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            cycles++;
            let curr = i;
            while (!visited[curr]) {
                visited[curr] = true;
                curr = posMap.get(nums[curr]);
            }
        }
    }
    
    return n - cycles;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大O表示法
时间复杂度O(n log n)
空间复杂度O(n)
  • 时间复杂度：O(n log n)，主要来自排序操作和数位和计算
  • 空间复杂度：O(n)，用于存储排序数组、哈希表映射和访问数组