561.数组拆分

目录

• 题目
• 解法
• 从尾部赋值
• 基数排序怎么处理负数的情况

题目

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。

返回该 最大总和 。

解法

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int i = 0; i < nums.size(); i += 2) {
            ans += nums[i];
        }
        return ans;
    }
};

从尾部赋值

我从头部赋值与逆向遍历有什么区别？
好的，我们来分析同样的例子 nums = {329, 457, 657, 839, 436, 720, 355}，这次通过正向遍历的方式来处理个位数的排序，看看结果会有什么不同。

示例前提

• 当前数组：nums = {329, 457, 657, 839, 436, 720, 355}
• 当前位数：个位数（exp = 1）
• 各个位数为：9, 7, 7, 9, 6, 0, 5

步骤 1：统计个位数的频次

和之前一样，统计个位数频次的结果为：

个位数:    0  1  2  3  4  5  6  7  8  9
频次统计:   1  0  0  0  0  1  1  2  0  2

步骤 2：转换为前缀和数组

将 cnt 数组转换为前缀和数组，得到每个个位数在排序后的位置范围：

前缀和:    1  1  1  1  1  2  3  5  5  7

步骤 3：正向遍历并放置元素

接下来，我们从 nums 的第一个元素开始正向遍历，将每个元素放入 buf 数组对应的位置：

1. i = 0: nums[0] = 329，个位数是 9。

   • 将 329 放在 cnt[9] - 1 = 6 的位置。
   • 更新 cnt[9]--，新值为 6。

2. i = 1: nums[1] = 457，个位数是 7。

   • 将 457 放在 cnt[7] - 1 = 4 的位置。
   • 更新 cnt[7]--，新值为 4。

3. i = 2: nums[2] = 657，个位数是 7。

   • 将 657 放在 cnt[7] - 1 = 3 的位置。
   • 更新 cnt[7]--，新值为 3。

4. i = 3: nums[3] = 839，个位数是 9。

   • 将 839 放在 cnt[9] - 1 = 5 的位置。
   • 更新 cnt[9]--，新值为 5。

5. i = 4: nums[4] = 436，个位数是 6。

   • 将 436 放在 cnt[6] - 1 = 2 的位置。
   • 更新 cnt[6]--，新值为 2。

6. i = 5: nums[5] = 720，个位数是 0。

   • 将 720 放在 cnt[0] - 1 = 0 的位置。
   • 更新 cnt[0]--，新值为 0。

7. i = 6: nums[6] = 355，个位数是 5。

   • 将 355 放在 cnt[5] - 1 = 1 的位置。
   • 更新 cnt[5]--，新值为 1。

最终结果

正向遍历得到的 buf 数组为：

buf = {720, 355, 436, 657, 457, 839, 329}

对比结果

与逆向遍历得到的结果 buf = {720, 355, 436, 457, 657, 329, 839} 相比，正向遍历破坏了排序的稳定性。例如：

• 数组中个位为 7 的两个数 457 和 657，在逆向遍历中，它们的相对顺序（457 在 657 之前）得到了保持；
• 而在正向遍历中，657 排在了 457 之前，导致相对顺序被打乱，破坏了基数排序的稳定性。

因此，在基数排序中使用逆向遍历可以确保同一位上相同数字的相对顺序不变，从而实现稳定排序。

基数排序怎么处理负数的情况

很麻烦，对于这题，本来想尝试一下的，还是用个内置函数吧