ArrayPartitionI [source code]

public class ArrayPartitionI {
    public int arrayPairSum(int[] nums) {
        int length = nums.length;
        if (length % 2 != 0) {
            System.out.println("Illegal Input");
            System.exit(1);
        }
        int n = length / 2; 
        Arrays.sort(nums);
        int res = 0;
        for (int i = 0; i < length; i += 2) res += nums[i];
        return res; 
    }
}

这个算法应该是比较直接的一个算法了.
这个问题的话, 最后写出来的代码很简单, 关键是对问题的理解.
这个问题穷搜肯定是不行的.
为了帮助理解, 还是按照例子来, 这里1432得到的结果是(1,2)和(3,4).
那么为什么(1,3)和(2,4)不行?
更进一步理解, 可以发现最后每一个pair 里面实际能参加到加法里面的其实只有1个数.
那么相应的, 最后...我这里的思路是想要用 contradiction 来证明,但是发现好像不是很好证明, 下面是 Leetcode上面别人给的证明:
Let me try to prove the algorithm...

Assume in each pair i, bi >= ai.
Denote Sm = min(a1, b1) + min(a2, b2) + ... + min(an, bn). The biggest Sm is the answer of this problem. Given 1, Sm = a1 + a2 + ... + an.
Denote Sa = a1 + b1 + a2 + b2 + ... + an + bn. Sa is constant for a given input.
Denote di = |ai - bi|. Given 1, di = bi - ai. Denote Sd = d1 + d2 + ... + dn.
So Sa = a1 + a1 + d1 + a2 + a2 + d2 + ... + an + an + di = 2Sm + Sd => Sm = (Sa - Sd) / 2. To get the max Sm, given Sa is constant, we need to make Sd as small as possible.
So this problem becomes finding pairs in an array that makes sum of di (distance between ai and bi) as small as possible. Apparently, sum of these distances of adjacent elements is the smallest. If that's not intuitive enough, see attached picture. Case 1 has the smallest Sd.

不得不承认这个证明还是简单聪明的.

让人吃惊的是, 这个问题还有一个更加快的解法, 基本是最速解法, 不依赖 sorting:

class Solution {  
public:  
    int arrayPairSum(vector<int>& nums) {  
        vector<int> hashtable(20001,0);  
        for(size_t i=0;i<nums.size();i++)  
        {  
            hashtable[nums[i]+10000]++;  
        }  
        int ret=0;  
        int flag=0;  
        for(size_t i=0;i<20001;){  
            if((hashtable[i]>0)&&(flag==0)){  
                ret=ret+i-10000;  
                flag=1;  
                hashtable[i]--;  
            }else if((hashtable[i]>0)&&(flag==1)){  
                hashtable[i]--;  
                flag=0;  
            }else i++;  
        }  
        return ret;  
    }  
};

这个代码的大概原理好像就是bucket sort, 因为知道所有 integer 的范围. 不过这里有些C++的东西不太看得懂, leetcode 解答那里还有一些改进版本的代码, 不过因为看不太懂C++, 而且对bucket sort本身其实也忘的差不多了, 所以这个问题暂时先不管了. 等以后回笼的时候重新思考;

这里顺便思考一下后面复习两本算法书的顺序, 应该是 CLRS 大于 sedgwick, 虽然 CLRS 会难一些, 不过 CLRS 讲的还是更好很多; 而且 sedgwick 主要也是为了看代码, 代码真正需要看完全可以去 booksite 或者g4g上面看, google 起来也更快;

大概知道这个代码的意思了, 尝试写一下Java 版本.

Problem 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:  
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:

• n is a positive integer, which is in the range of [1, 10000].
• All the integers in the array will be in the range of [-10000, 10000].
  Subscribe to see which companies asked this question.

Hide Tags Array