C, 0mS, Sort + O(1) Space Comparison


  • 0
    M

    The overall approach given here is the typical one : Transform integers into strings, sort them and then concatenate.

    Main function implementation is given below:

    char *largestNumber(int* nums, int numsSize)
    {
        int i, ssize = 0, slen;
        char *ch = NULL, *tch;
        char **cstr = NULL;
    
        /* Validate */
        if (!nums || numsSize < 1 ||
            !(cstr = malloc( numsSize * sizeof(char *) +
                            (numsSize * MAX_STR_SZ))))
            goto __lexit;
        tch = (char *)(cstr + numsSize);
    
        /* Convert integers into strings */
        for (i = 0; i < numsSize; ++i){
            cstr[i] = tch; // assign the previously allocated memory
            if (!(slen = sprintf(cstr[i],"%d",nums[i])))
                goto __lexit;
            tch += MAX_STR_SZ; // move to the next location
            ssize += slen;
        }
    
        /* Sort the strings */
        QuickSort(cstr, 0, numsSize - 1);
    
        /* Allocate space for the string */
        if (!(ch = malloc(sizeof(char) * (ssize + 1))))
            goto __lexit;
    
        /* Save the values into the string */
        strcpy(ch, cstr[0]);
        slen = strlen(cstr[0]);
        if ((cstr[0])[0] != '0')
            for (i = 1; i < numsSize; ++i) {
                strcat(&ch[slen], cstr[i]);
                slen += strlen(cstr[i]);
            }
    __lexit:
        if (cstr) free(cstr);
        return ch;
    }
    

    Comparison function used for quick sort requires us to identify the string with a larger leading character, essentially the larger MSB. For strings of equal length, we can merely loop and compare, quite straightforward. But we need to also handle the cases where one is a substring of the other. Here we can loop back the smaller string and continue the same comparison loop.

    The recursive function implementing the same is given below:

    int CompareStr(char *s1, char *s2)
    {
        char *ts1 = s1, *ts2 = s2;
    
        /* Loop while both the strings are valid and equal */
        while (*ts1 && *ts2 && *ts1 == *ts2) {
            ts1++;
            ts2++;
        }
    
        /* If they are both valid or both are NULL, then return the
        difference */
        if ((*ts1 && *ts2) || (!*ts1 && !*ts2))
            return (int) *ts1 - *ts2;
    
        /* Else if only one of them is valid, then loop back and continue 
        the scan */
        else if (*ts1)
            return CompareStr(ts1, s2); // loop back the 2nd string
        else
            return CompareStr(s1, ts2);
    }
    

    An iterative implementation of the same idea:

    int CompareStr(char *s1, char *s2)
    {
        char *ts1 = s1, *ts2 = s2;
    
        /* Loop while either of these strings are valid. The idea is to
        catch the string with the bigger leading characters.*/
        while (*ts1 || *ts2) {
            /* If both the strings are valid, then either scan forward or
            break to return the difference. */
            if (*ts1 && *ts2) {
                /* Equal */
                if (*ts1 == *ts2) {
                    ts1++;
                    ts2++;
                }
                /* Unequal */
                else if (*ts1 != *ts2)
                    break;
            }
            /* Else if only one of them is valid, then loop back and continue
            the scan */
            else if (*ts1)
                ts2 = s2;
            else
                ts1 = s1;
        }
        
        /* Return the difference */
        return (int)(*ts1 - *ts2);
    }
    

    Note that the time complexity of the above method would be O(n x m). Typically the number of comparisons should be equal to the LCM of n and m.

    Full source code at GitHub


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.