Perm函数及C语言移位统计程序无法处理长数字，求优化建议

需要实现程序：从标准输入读取自然数数量N，再读取N个自然数，统计其中可通过数字移位转换为其他输入数字的数量。示例输入：6，随后输入25 21 10242 42210 52 24021，输出应为5。

现有C语言代码存在两个问题：无法处理较长数字，且怀疑qsort并非最优方案，寻求改进建议。

现有代码 #

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

typedef unsigned long long int cache;

int cmp(const void * a, const void * b) {
    return ( *(int*)a - *(int*)b );
}

int main() {
    int n, i, j, count_equals = 0;
    char num[22];
    scanf("%d", &n);
    cache * A = (cache *) malloc(n * sizeof(cache));
    for (i = 0; i < n; i++) {
        scanf("%s", num);
        qsort(num, strlen(num), sizeof(char), cmp);
        for (A[i] = num[--j] - '0'; --j >= 0; A[i] = A[i] * 10 + (num[j] - '0'));
    }
    qsort(A, n, sizeof(cache), cmp);
    for (j = 0, i = 1; i < n; i++) {
        if (A[i] == A[i - 1]) { 
            count_equals++;
        } else if (count_equals) {
            j += ++count_equals, count_equals = 0;
        }
    }
    if (count_equals) {
        j += ++count_equals;
    } 
    free(A);
    printf("%d\n", j);
    return 0;
}

改进建议 #

1. 解决长数字溢出问题 #

原代码用unsigned long long存储排序后的数字，当数字长度超过19位时会溢出（unsigned long long最大值为18446744073709551615，仅20位，有效数字最多19位）。优化方案：

• 直接用字符串保存排序后的数字作为特征键，无论数字多长都不会溢出，无需转换为数值类型。
• 修复原代码中j未初始化的bug：在生成特征键前，必须先将j赋值为字符串长度，否则会出现数组越界的未定义行为。

2. 替换qsort的更优方案：哈希表统计 #

原代码两次使用qsort，时间复杂度为O(N log N + NM log M)（M为数字平均长度）。改用哈希表统计相同特征键的数字数量，平均时间复杂度可优化为O(NM log M)：

• 哈希表的插入、查找操作平均时间复杂度为O(1)，无需对所有特征键排序，仅需对每个数字的字符排序生成特征键。
• 遍历哈希表时，对每个出现次数≥2的特征键，累加其出现次数即可得到符合条件的数字总数。

改进后的示例代码 #

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

// 哈希表节点结构
typedef struct HashNode {
    char* key;
    int count;
    struct HashNode* next;
} HashNode;

// 字符串哈希函数
unsigned int hash(const char* str) {
    unsigned int h = 0;
    while (*str) {
        h = h * 31 + *str++;
    }
    return h % 1009; // 选用质数作为哈希表大小，减少冲突
}

// 在哈希表中查找键，不存在则插入新节点
HashNode* find_or_insert(HashNode** table, const char* key) {
    unsigned int idx = hash(key);
    HashNode* node = table[idx];
    while (node) {
        if (strcmp(node->key, key) == 0) {
            return node;
        }
        node = node->next;
    }
    // 插入新节点
    node = (HashNode*)malloc(sizeof(HashNode));
    node->key = strdup(key);
    node->count = 1;
    node->next = table[idx];
    table[idx] = node;
    return node;
}

// 字符排序比较函数
int cmp_char(const void* a, const void* b) {
    return *(char*)a - *(char*)b;
}

int main() {
    int n, i, result = 0;
    char num[100]; // 支持更长的数字输入
    HashNode* hash_table[1009] = {NULL}; // 初始化哈希表

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%s", num);
        int len = strlen(num);
        qsort(num, len, sizeof(char), cmp_char); // 生成特征键：排序后的字符数组
        HashNode* node = find_or_insert(hash_table, num);
        node->count++;
    }

    // 遍历哈希表统计结果
    for (i = 0; i < 1009; i++) {
        HashNode* node = hash_table[i];
        while (node) {
            if (node->count >= 2) {
                result += node->count;
            }
            // 释放内存
            HashNode* temp = node;
            node = node->next;
            free(temp->key);
            free(temp);
        }
    }

    printf("%d\n", result);
    return 0;
}

内容的提问来源于stack exchange，提问作者mitko