leetcode-561 Array Partition I

561. Array Partition I

Description

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:

1
2
3
4
Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:

  1. n is a positive integer, which is in the range of [1, 10000].
  2. All the integers in the array will be in the range of [-10000, 10000].

Analyse

将输入的序列分为两部分，a和b

最大化 $\sum_i min(a_i, b_i)$

取序列里一半的数，比另一半小，最大的数不能取，于是取第二大的，第三大的不能取，取第四大的，以此类推就能得到这个分组

先将nums排序，然后取第0，2，4，6，…，2n个元素，加起来就是最大的$\sum_i min(a_i, b_i)$

时间复杂度
sort排序，没有研究过代码实现，据各种博客说是多种排序算法的混合，时间复杂度可以算成 $O(nlogn)$

整个函数的时间复杂度 $O(nlogn)$

空间复杂度 $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
int arrayPairSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());

    int sum = 0;

    for(int i = 0; i < nums.size(); i+=2)
    {
        sum += nums[i];
    }

    return sum;
}

看了下LeetCode上用时最短的版本，可以看到这位大佬的第一个版本和我的思路一样，但注释了然后写出了一个更快的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int arrayPairSum(vector<int>& nums) {
    // 1, 2, 3, 11
    // sort(nums.begin(), nums.end());
    // int s = 0;
    // for (int i = 0; i < nums.size(); i += 2)
    //     s += nums[i];
    // return s;

    int f[20001] = {};
    for (int i = 0; i < nums.size(); ++i)
        ++f[10000 + nums[i]];

    int sum = 0;
    int c = 0;
    for (int i = 0; c < nums.size() - 1; ++i) {
        int k = (f[i] + 1 - (c & 0x01)) >> 1;
        sum += (i - 10000)*k;
        c += f[i];
    }

    return sum;
}

不太明白，举个例子看看效果 nums = {1，2，3，11}

1
2
int f[20001] = {};
for (int i = 0; i < nums.size(); ++i) ++f[10000 + nums[i]];

f的长度为20001是因为nums中元素的取值范围是[-10000, 10000]

f的后10000位存储nums中各个元素出现的次数

f[10001] = 1
f[10002] = 1
f[10003] = 1
f[10011] = 1

1
2
3
4
5
6
7
int sum = 0;
int c = 0;
for (int i = 0; c < nums.size() - 1; ++i) {
    int k = (f[i] + 1 - (c & 0x01)) >> 1;
    sum += (i - 10000)*k;
    c += f[i];
}

这个例子{1，2，3，11}中都是正数，直接从f[10000]开始看，之前的循环都是0

i k sum c
9999 (f[9999] + 1 - (0 & 0x01)) >> 1 = 0 sum = sum + (9999 - 10000) * 0 = 0 c = c + f[9999] = 0
10000 (f[10000] + 1 - (0 & 0x01)) >> 1 = 0 sum = sum + (10000 - 10000) * 0 = 0 c = c + f[10000] = 0
10001 (f[10001] + 1 - (0 & 0x01)) >> 1 = 1 sum = sum + (10001 - 10000) * 1 = 1 c = c + f[10001] = 1
10002 (f[10002] + 1 - (1 & 0x01)) >> 1 = 0 sum = sum + (10002 - 10000) * 0 = 1 c = c + f[10002] = 2
10003 (f[10003] + 1 - (2 & 0x01)) >> 1 = 1 sum = sum + (10003 - 10000) * 1 = 4 c = c + f[10003] = 3

到这里c的值为3，退出循环，输出sum = 4

我终于看明白了，和我写的一个意思

注意到在i为1，2，3的时候k为1，0，1，乘起来求和就是sum，c用来记录已经检测的nums里的值的个数, c < nums.size() - 1时就可以结束了，最后一个值不用看，最后返回sum

Reference

  1. http://www.cplusplus.com/reference/algorithm/sort/