Create Maximum Number

07/18/2016 Dynamic Programming Greedy

Question

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:

nums1 = [3, 4, 6, 5]

nums2 = [9, 1, 2, 5, 8, 3]

k = 5

return [9, 8, 6, 5, 3]

Example 2:

nums1 = [6, 7]

nums2 = [6, 0, 4]

k = 5

return [6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9]

nums2 = [8, 9]

k = 3

return [9, 8, 9]


Solution

Result: Accepted Time: 44 ms

Here should be some explanations.

#define  MAXN 65535
#define START 1
#define END 2
#define PTR 3

int a_index[MAXN], b_index[MAXN];
int a_idx[10][4], b_idx[10][4];
int a_max[MAXN], b_max[MAXN];
int ans[MAXN], tmp_ans[MAXN];

void init_index(int data[], int index[], int idx[10][4], int cnt)
{
    memset(idx, 0, sizeof(a_idx));
    for(int i = 0; i < cnt; i++)
        idx[data[i]][0]++;
    idx[9][END] = idx[9][START] = 0 ;
    for(int i = 8; i >= 0; i--)
        idx[i][END] = idx[i][START] = idx[i+1][START] + idx[i+1][0];
    for(int i = 0; i < cnt; i++)
        index[idx[data[i]][END]++] = i;
}

void init(int a[], int acnt, int b[], int bcnt)
{
    init_index(a,a_index,a_idx,acnt);
    init_index(b,b_index,b_idx,bcnt);
}

void get_len_max(int ans[],int data[], int index[], int idx[10][4], int cnt, int len)
{
    if(len == cnt)
    {
        for(int i = 0; i < cnt; i++)
            ans[i] = data[i];
        return;
    }
    int exist[10] = {0};
    for(int i = 0; i < 10; i++)
    {
        idx[i][PTR] = idx[i][START];
        exist[i] = idx[i][0];
    }
    for(int i = 0; len > 0; i++, len--)
        for(int j = 9; j >= 0; j--)
        {
            if( exist[j] > 0 && cnt - index[idx[j][PTR]] >= len)
            {
                ans[i] = j;
                exist[j] --;
                int mx = index[idx[j][PTR]];
                idx[j][PTR]++;
                for(int t = 0; t < 10; t++)
                    while(exist[t] > 0 && index[idx[t][PTR]] < mx)
                    {
                        idx[t][PTR] ++;
                        exist[t] --;
                    }
                break;
            }
        }
}

bool compare(int * a, int a_cnt, int *b, int b_cnt)
{
    int ptr = 0;
    while(ptr < a_cnt && ptr < b_cnt && a[ptr] == b[ptr]) ptr++;
    if(ptr == a_cnt || ptr == b_cnt)
        return ptr != a_cnt;
    return a[ptr] > b[ptr];
}

void merge_max(int ans[], int a_max[], int a_cnt, int b_max[], int b_cnt, int k)
{
    for(int i = 0, aptr = 0, bptr = 0; i < k; i++)
        if(compare(a_max+aptr,a_cnt-aptr,b_max+bptr,b_cnt-bptr))
            ans[i] = a_max[aptr++];
        else
            ans[i] = b_max[bptr++];
}

void update_ans(int* ans, int* tmp_ans, int cnt)
{
    int ptr = 0;
    while(ptr < cnt && ans[ptr] == tmp_ans[ptr] ) ptr++;
    if(ptr == cnt || ans[ptr] > tmp_ans[ptr])
        return ;
    while(ptr < cnt)
    {
        ans[ptr] = tmp_ans[ptr];
        ptr++;
    }
}

void deal(int *a, int a_cnt, int* b, int b_cnt,int k)
{
    init(a,a_cnt,b,b_cnt);
    int a_start = 0, a_end = a_cnt;
    if(k > b_cnt )
        a_start = k - b_cnt;
    if(k < a_cnt )
        a_end = k;
    memset(ans,0,sizeof(int)*k);
    for(int i = a_start; i <= a_end; i++)
    {
        get_len_max(a_max,a,a_index,a_idx,a_cnt,i);
        get_len_max(b_max,b,b_index,b_idx,b_cnt,k-i);
        merge_max(tmp_ans,a_max,i,b_max,k-i,k);
        update_ans(ans,tmp_ans,k);
    }
}

int* maxNumber(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int* returnSize) {
    deal(nums1,nums1Size,nums2,nums2Size,k);
    int * ret = malloc(sizeof(int)*(k));
    *returnSize = k;
    for(int i = 0; i < k; i++)
        ret[i] = ans[i];
    return ret;
}

/**
[6,7]
[6,0,4]
5

[3,4,8,9,3,0]
[6,1,9,1,1,2]
6
[3,3,3,2,3,7,3,8,6,0,5,0,7,8,9,2,9,6,6,9,9,7,9,7,6,1,7,2,7,5,5,1]
[5,6,4,9,6,9,2,2,7,5,4,3,0,0,1,7,1,8,1,5,2,5,7,0,4,3,8,7,3,8,5,3,8,3,4,0,2,3,8,2,7,1,2,3,8,7,6,7,1,1,3,9,0,5,2,8,2,8,7,5,0,8,0,7,2,8,5,6,5,9,5,1,5,2,6,2,4,9,9,7,6,5,7,9,2,8,8,3,5,9,5,1,8,8,4,6,6,3,8,4,6,6,1,3,4,1,6,7,0,8,0,3,3,1,8,2,2,4,5,7,3,7,7,4,3,7,3,0,7,3,0,9,7,6,0,3,0,3,1,5,1,4,5,2,7,6,2,4,2,9,5,5,9,8,4,2,3,6,1,9]
160
*/

Complexity Analytics

  • Time Complexity:
  • Space Complexity: