For example, consider an array a[10] = {1, 2, 3, 4, 1, 2, 3, 4, 5, 6, 7}. The task is to count the number of distinct elements, which in this case would be {1, 2, 3, 4, 5, 6, 7}, totaling seven unique values. Similarly, in web analytics, you may want to track individual users like "Xiaoming" with out repeatedly counting their visits, ensuring only new visitors increment the total count.

A common problem involves counting distinct characters in a string, such as "abcdaaabceeda". A brute-force approach would involve repeatedly traversing the string to check if each character has already been encountered, but this method is inefficient. Instead, we can use a hash table or a bitmap to optimize the process.

Hash Table Implementation

Using a hash table, we can efficiently count distinct lowercase letters by initializing an array of size 26 (one for each letter) and marking occurrences:

#include <stdio.h>
#include <string.h>

int main() {
    char str[] = "abcdaaabceeda";
    int hash[26] = {0};
    int length = strlen(str);
    
    for (int i = 0; i < length; ++i) {
        int index = str[i] - 'a';
        hash[index]++;
    }

    int uniqueCount = 0;
    for (int i = 0; i < 26; ++i) {
        if (hash[i] > 0) {
            uniqueCount++;
        }
    }

    printf("Unique Count: %d\n", uniqueCount);
    return 0;
}

This implementation uses a simple array to store the frequency of each character, allowing us to calculate the number of unique characters in a single pass.

Bitmap Optimizaton

To save memory, we can use a bitmap instead of a full hash table. A bitmap uses fewer bits to represent presence or absence of specific elements:

#include <stdio.h>
#include <string.h>

int bitCount(unsigned int bitmap) {
    unsigned int temp = bitmap;
    temp = (temp & 0x55555555) + ((temp & 0xAAAAAAAA) >> 1);
    temp = (temp & 0x33333333) + ((temp & 0xCCCCCCCC) >> 2);
    temp = (temp & 0x0F0F0F0F) + ((temp & 0xF0F0F0F0) >> 4);
    temp = (temp & 0x00FF00FF) + ((temp & 0xFF00FF00) >> 8);
    temp = (temp & 0x0000FFFF) + ((temp & 0xFFFF0000) >> 16);
    return temp;
}

int main() {
    char str[] = "abcdaaabceeda";
    unsigned int bitmap = 0;
    int length = strlen(str);

    for (int i = 0; i < length; ++i) {
        int pos = str[i] - 'a';
        bitmap |= (1 << pos);
    }

    printf("Unique Count: %d\n", bitCount(bitmap));
    return 0;
}

The bitmap approach reduces memory usage significantly since it only tracks the presence of each character rather than storing counts. However, it cannot provide detailed frequency information.

In practical applications, such as visitor tracking on websites, hash functions are used to map user identifiers (e.g., "Xiaoming") to unique addresses in a hash table or bitmap. These structures enable efficient updates and queries, making them ideal for real-time data processing.