ArrayPartitionIOPT [source code]

public class ArrayPartitionIOPT {
    public int arrayPairSum(int[] nums) {
        int[] b = new int[20001];
        for (int i = 0; i < nums.length; i++) {
            b[nums[i] + 10000]++;
        }
        int ret = 0;
        int flag = 0;
        for (int i = 0; i < 20001; ) {
            if ((b[i] > 0) && (flag == 0)) {
                ret += i - 10000;
                flag = 1;
                b[i]--;
            } else if ((b[i] > 0) && (flag == 1)) {
                b[i]--;
                flag = 0;
            } else i++;
        }
        return ret;
    }
}

代码模板:

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;  
    }  
};

这个代码是 Okay 的, 98%的速度, 比之前那个简单依靠 sort 的快很多(那个是40%左右);

感觉这种实际写 leetcode 的时候碰到问题, 然后去类似g4g这样的网站学习算法, 然后实现一下, 学起来的算法牢靠很多;

这里的buckets 可以直接用一个 array, 是因为这个代码并不像传统的BucketSort一样, 全部 push 进去, 而是只是单纯的在 bucket 里面存一个 counter, 所以这个直接一个数组就可以了 (array 本身也可以理解为一个简化版的hashtable);

整个算法的核心思想并不复杂, 就是用bucketsort进行sorting, 然后最后 concatenation 这一步, 是整个算法的variation 所在. 使用一个 flag, 来完成一个跳子的过程, 比如如果 input 是123456, 最后就是只有135被算到ret 里面了;
更深入一点, 如果使用类似 mod 的操作, 也可以完成更复杂的跳子操作, 这里的是1/2的跳子, 类似的1/3之类的跳子也可以完成;

更深入的思考, 为什么这个算法比普通的标准 sort 的算法要快很多? 按理说这个算法本身也是一个 sort 啊?这个原因就是因为bucket sort本身就是比普通的comparison-based的算法要快很多; 至于这个快的原因, 一定原因上是因为, 比如nums[i]被放到了b[nums[i]+10000]里面, nums 里面的 value 被当成 index 使用了. 所以可以认为这个加速是来自于利用 array 的direct addressing (by index).

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