Thursday, July 9, 2015

LeetCode OJ - Merge Sorted Array

Problem:

Please find the problem here.

Solution:

The key idea to this problem is that the end of the first array has space, so we will start there. The maximum element should go to the last, and then we moves the pointers around.

Let say we have the arrays [1,3,5,_,_._] and [2,4,6]. The algorithm works as follow:

f, s, t are simply variables pointing to the end of the first array, end of the second array, and end of the free space, respectively.

1,3,5,_,_,_
    f     t

2,4,6
    s

The maximum value can be found as the maximum of the two tails. So we know the maximum value is 6, so we move it to the free space, so it becomes this

1,3,5,_,_,6
    f   t

2,4,6
  s

The rest just follows, this time on the first array

1,3,5,_,5,6
  f   t

2,4,6
  s

Be careful if f or s underflow, and so be it. 

The key to the correctness of the algorithm is to prove that the number of free spaces is always equals to the number of elements not consumed in the second array. This is true initially and is true regardless of whether we choose the first array or second array for every step, so we can induce the algorithm is correct.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/merge-sorted-array/

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

using namespace std;

namespace _LEET_MERGE_SORTED_ARRAY
{
    class Solution
    {
    public:
        void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
        {
            int f = m - 1;
            int s = n - 1;
            int t = m + n - 1;
            while (f >= 0 || s >= 0)
            {
                if (f == -1)
                {
                    nums1[t--] = nums2[s--];
                }
                else if (s == -1)
                {
                    nums1[t--] = nums1[f--];
                }
                else if (nums1[f] > nums2[s])
                {
                    nums1[t--] = nums1[f--];
                }
                else
                {
                    nums1[t--] = nums2[s--];
                }
            }
        }
    };
};

using namespace _LEET_MERGE_SORTED_ARRAY;

int LEET_MERGE_SORTED_ARRAY()
{
    Solution s;
    int first[6] = { 1, 3, 5, 0, 0, 0 };
    int second[3] = { 2, 4, 6 };
    vector<int> firstVector(first, first + 6);
    vector<int> secondVector(second, second + 3);
    s.merge(firstVector, 3, secondVector, 3);
    for (int i =0 ; i < 6; i++)
    {
        cout << firstVector[i];
    }
    return 0;
}

No comments :

Post a Comment