LeetCode 561. 数组拆分 I

梦里梦外; 2022-11-08 14:21 112阅读 0赞

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

返回该 最大总和 。

思路是将数组排序，之后取偶数位的和：

void quickSort(vector<int> &nums, size_t l, size_t r) { 
            if (l >= r) { 
                return;
            }
    
            default_random_engine e;
            uniform_int_distribution<size_t> u(l, r);
            size_t randIndex = u(e);
            swap(nums[randIndex], nums[r]);
            size_t small = l, cur = l;
    
            while (cur < r) { 
                if (nums[cur] < nums[r]) { 
                    swap(nums[cur], nums[small]);
                    ++small;
                } 
                ++cur;
            }
            swap(nums[small], nums[r]);
    
            if (small != l) { 
                quickSort(nums, l, small - 1);
            }
            if (small != r) { 
                quickSort(nums, small + 1, r);
            }
        }
    
        int arrayPairSum(vector<int>& nums) { 
            size_t sz = nums.size();
            quickSort(nums, 0, sz - 1);
    
            int sum = 0;
            for (size_t i = 0; i < sz; i += 2) { 
                sum += nums[i];
            }
            return sum;
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，112人围观）

还没有评论，来说两句吧...

相关阅读

相关 C语言重构【561】数组拆分 I

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

r囧r小猫/ 2022年11月21日 11:46/ 0 赞/ 121 阅读

相关 LeetCode 561. 数组拆分 I

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

梦里梦外;/ 2022年11月08日 14:21/ 0 赞/ 113 阅读

相关（js）leetcode561. 数组拆分 I

题目： > 给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从

痛定思痛。/ 2022年10月29日 15:22/ 0 赞/ 105 阅读

相关 leetcode 561. 数组拆分 I（Java版）

题目 [https://leetcode-cn.com/problems/array-partition-i/][https_leetcode-cn.com_proble

刺骨的言语ヽ痛彻心扉/ 2022年10月15日 12:55/ 0 赞/ 129 阅读

相关 561. 数组拆分 I

> 给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n

￡神魔★判官ぃ/ 2022年10月05日 03:57/ 0 赞/ 124 阅读

相关 561. 数组拆分

Leetcode链接：[561. 数组拆分][561.] 题目描述给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 `(a1, b1)

以你之姓@/ 2022年09月07日 05:55/ 0 赞/ 119 阅读

相关 561 数组拆分 I（贪心）

1. 问题描述：给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得

我不是女神ヾ/ 2022年08月31日 07:21/ 0 赞/ 134 阅读

相关 LeetCode561. 数组拆分 I

给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从1 到 n 的 min(ai,

Bertha 。/ 2022年05月23日 10:14/ 0 赞/ 127 阅读

相关 LeetCode 561 数组拆分I

题目描述：给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从1 到 n 的 m

小咪咪/ 2022年04月06日 06:54/ 0 赞/ 150 阅读

相关 leetcode:561. 数组拆分 I

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

男娘i/ 2022年02月13日 05:11/ 0 赞/ 152 阅读