数组拆分

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

返回该 最大总和 。

示例 1：
输入：nums = [1,4,3,2]
输出：4
解释：所有可能的分法（忽略元素顺序）为：
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大总和为 4

示例 2：
输入：nums = [6,2,6,5,1,2]
输出：9
解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

提示：
1 <= n <= 104
nums.length == 2 * n
-104 <= nums[i] <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/array-partition-i
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i += 2) {
            sum += nums[i];
        }
        return sum;
    }
}

计数排序

public class Solution {
    public int arrayPairSum(int[] nums) {
        int[] arr = new int[20001];
        int lim = 10000;
        for (int num: nums)
            arr[num + lim]++;
        int d = 0, sum = 0;
        for (int i = -10000; i <= 10000; i++) {
            sum += (arr[i + lim] + 1 - d) / 2 * i;
            d = (2 + arr[i + lim] - d) % 2;
        }
        return sum;
    }
} 
作者：LeetCode
链接：https://leetcode-cn.com/problems/array-partition-i/solution/shu-zu-chai-fen-i-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
for(int i = -10000; i <= 10000; i++ ){
  int count = arr[i + lim];
  if(count != 0){
      //count + 1是为了让奇数在/2时能向上取整
      //如果d是1, 也就说明这个数的个数被上一次分配占用了一个, 对偶数没有影响
      //但是对奇数, 因为少了一个, 所以还剩偶数个, 所以需要再-d, 实质就是-1, 否则会多分配一对
      sum += (count + 1 - d) / 2 * i;
      //d就是用来说明这次分配有没有占用下个数的个数, 如果有, 则置1
      //要-d是因为要考虑上次分配有没有占用这次的个数, 如果占用了, 那就-1, 也就是-d
      //+2是因为  防止count == 1 || count == 0
      d = (count - d + 2) & 1;
  }
}

参考文献

ibuyan的评论

赏

谢谢你请我吃糖果

微信