Sunday, April 23, 2017

LeetCode OJ - Array Partition I

Problem:

Please find the problem here.

Analysis:

The problem is trivial if there is only 1 pair.

If there are 2 pairs, you always do (a, b) (c, d) assuming $ a < b < c < d $.

With more pairs, the idea is to sort the data first, and then pairing them up in order.

It is trivial to argue that you have to take $ a $ because eventually it has to be in a pair. You can't pick $ d $ regardless because it will lose in any pairs, my only option is picking $ b $ or $ c $, and the answer is obvious.

However, this argument doesn't generalize. We need something else to prove the idea works.

Solution:

The algorithm is greedy, so maybe we should think about proof strategy for greedy algorithms. Here is my idea, greedy stay ahead.

Let's report the pairs from the back of the array, we first report the (second largest, largest) pair. There is no way another other algorithm can produce any pair better than this one.

By induction, we can assume the algorithm stay ahead for $ k $ step, now the algorithm lose in the $ k + 1 $ step, the only possibility is that the other algorithm somehow found a pair that is better than what my algorithm provides, but that is impossible because it is the largest possible.

I know my language is not rigorous, but you get the point, do you?

With that, the code is very simple.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/array-partition-i/

#include "LEET_ARRAY_PARTITION_I.h"
#include <map>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_ARRAY_PARTITION_I
{
    class Solution {
    public:
        int arrayPairSum(vector<int>& nums)
        {
            int result = 0;
            sort(nums.begin(), nums.end());
            for (size_t i = 0; i < nums.size(); i += 2)
            {
                result += nums[i];
            }
            return result;
        }
    };
};

using namespace _LEET_ARRAY_PARTITION_I;

int LEET_ARRAY_PARTITION_I()
{
    Solution solution;
    vector<int> nums;
    nums.push_back(1);
    nums.push_back(2);
    nums.push_back(3);
    nums.push_back(4);
    cout << solution.arrayPairSum(nums) << endl;
    return 0;
}

No comments :

Post a Comment