[OJ] Careercup Top 150(1.3): Solution: 1. O(n^2): loop directly to remove duplicate, then compact. 2. O(lg n): sort then remove duplicate, then compact.

remove_duplicate.cpp

// O(n^2) solution
void remove_duplicate(char* s)
{
    const int size = strlen(s);
    for (int i = 0; i < size - 1; ++i)
    {
        if (s[i] == '\0')
        {
            continue;
        }
        for (int j = i + 1; j < size; ++j)
        {
            if (s[i] == s[j])
            {
                s[j] = '\0';
            }
        }
    }
    
    compact(s, size);
}

void compact(char* s, const int size)
{
    int count = 0;
    for (int i = 0; i < size; ++i)
    {
        if (s[i] != '\0')
        {
            s[count++] = s[i];
        }
    }
    s[count] = '\0';
}

// O(lg n) solution
int char_cmp(void* a, void* b)
{
    const char c_a = *(char*)a;
    const char c_b = *(char*)b;
    return c_a - c_b;
}

void remove_duplicate2(char* s)
{
    const int size = strlen(s);
    qsort(s, size, sizeof(char), &char_cmp);
    
    for (int i = 0; i < size - 1; ++i)
    {
        if (s[i] == s[i + 1])
        {
            s[i] = '\0';
        }
    }
    
    compact(s, size);
}