电话号码重复检测题解

题解：电话号码重复检测与统计

问题描述

给定若干电话号码，其中包含字母、数字和连接符 -，需要将这些电话号码规范化为数字形式，并检测重复的电话号码。最终需要输出：

1. 格式不正确的电话号码（包括不含 3 或 6 作为开头的号码）。
2. 检测并统计重复出现的电话号码，按格式输出重复次数。

输入描述

• 输入若干行，每行一个包含字母、数字、连接符 - 的字符串，代表一个电话号码。

输出描述

• 输出所有格式错误的电话号码。
• 输出所有重复的电话号码及其出现次数。如果没有错误或重复，则输出 Not found.。

解决方案

1. 字符转换与处理

首先，将输入的电话号码进行转换：

• 字符串中的字母根据电话键盘的传统映射规则（例如 A, B, C 对应数字 2）转换为数字。
• - 连接符忽略。
• 非法字符（如 Q 和 Z）导致电话号码被认为格式错误。

2. 哈希表和位操作

使用一个位操作哈希表 storage 来记录出现过的电话号码：

• 每个电话号码经过处理后形成一个长整型数字，通过位操作哈希函数来检测该号码是否已经出现。
• 若号码首次出现，则在哈希表中进行标记。
• 若号码已经出现过，则记录在重复号码数组 repeatAns 中，并统计其出现次数。

3. 重复号码处理

将所有重复的电话号码记录在 repeatAns 数组中，并通过 qsort 进行排序。排序后的结果按格式输出电话号码及其重复次数。

代码实现

以下是实现该算法的完整代码：

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

unsigned char storage[250010] = {0};

typedef struct phoneNum {
    int num;
    short count;
} phoneNum;

phoneNum repeatAns[1510];
int repeatCount = 0;

int transferL2N(char c) {
    if (c == 'Q' || c == 'Z') return -1;
    if (c == '-') return -2;
    if (c >= 'A' && c <= 'C') return 2;
    if (c >= 'D' && c <= 'F') return 3;
    if (c >= 'G' && c <= 'I') return 4;
    if (c >= 'J' && c <= 'L') return 5;
    if (c >= 'M' && c <= 'O') return 6;
    if (c >= 'P' && c <= 'S') return 7;
    if (c >= 'T' && c <= 'V') return 8;
    if (c >= 'W' && c <= 'Y') return 9;
    if (c >= '0' && c <= '9') return c - '0';
    else return -1;
}

int stat(int initNum, int tailNum) {
    int a = (initNum / 3 - 1) * 125000 + tailNum / 8;
    int b = tailNum % 8;
    if (((storage[a] >> b) & 1) == 1) return 1;
    storage[a] = storage[a] | (1 << b);
    return 0;
}

int main() {
    char s[21];
    long long inputNumber;
    int c;
    int errorCount = 0;
    int findRepeat;
    printf("Error:\n");
    while (gets(s) != NULL) {
        inputNumber = 0;
        for (int i = 0; s[i] != '\0'; i++) {
            c = transferL2N(s[i]);
            if (c == -1) goto p;
            if (c != -2) inputNumber = inputNumber * 10 + c;
        }
        if (inputNumber / 1000000 != 3 && inputNumber / 1000000 != 6) goto p;
        findRepeat = 0;
        if (stat(inputNumber / 1000000, inputNumber % 1000000) == 1) {
            for (int j = 0; j < repeatCount; j++) {
                if (repeatAns[j].num == inputNumber) {
                    repeatAns[j].count++;
                    findRepeat = 1;
                    break;
                }
            }
            if (!findRepeat) {
                repeatAns[repeatCount].num = inputNumber;
                repeatAns[repeatCount].count = 2;
                repeatCount++;
            }
        }
        continue;
    p:
        printf("%s\n", s);
        errorCount = 1;
    }
    if (errorCount == 0) printf("Not found.\n");

    printf("\nDuplication:\n");
    int findSameNum = 0;
    qsort(repeatAns, repeatCount, sizeof(repeatAns[0]), [](const void *a, const void *b) -> int {
        return ((struct phoneNum *)a)->num > ((struct phoneNum *)b)->num;
    });
    for (int i = 0; i < repeatCount; i++) {
        printf("%d-%04d %d\n", repeatAns[i].num / 10000, repeatAns[i].num % 10000, repeatAns[i].count);
        findSameNum = 1;
    }
    if (!findSameNum) printf("Not found.\n");

    return 0;
}

4. 输出结果

在处理的过程中，程序将输出以下结果：

• 所有格式错误的电话号码。
• 所有重复的电话号码及其重复次数（如果有的话）。

5. 复杂度分析

• 输入字符串长度最大为20，且每次只需遍历一次字符串并转换成电话号码，因此时间复杂度为 O(n)。
• 对所有重复号码进行排序的复杂度为 O(k log k)，其中 k 为重复电话号码的数量。

总结

该程序高效地处理并检测了电话号码的重复情况，利用位操作和哈希表减少了空间占用，确保在大数据量下的可行性和性能。

新知识点

在这道题的实现中，qsort 的 cmp 函数内置写法和哈希表的应用是关键知识点，下面我们详细解释这两个知识点：

1. qsort 的 cmp 函数内置写法

在这段代码中，qsort 用于对重复的电话号码进行排序。排序的关键在于比较函数 cmp，它决定了排序的规则。在传统的 C++ 中，我们通常会定义一个比较函数，然后将其传递给 qsort。但是，在这个程序中，我们使用了内置的匿名函数（也称为 lambda 表达式）来简化 cmp 函数的编写。

qsort(repeatAns, repeatCount, sizeof(repeatAns[0]), [](const void *a, const void *b) -> int {
    return ((struct phoneNum *)a)->num > ((struct phoneNum *)b)->num;
});

关键点：

• 匿名函数：[](const void *a, const void *b) -> int 是一个匿名函数，也就是 lambda 表达式。它直接在代码中定义，不需要单独声明。
• 类型转换：(struct phoneNum *)a 将 void * 指针转换为 phoneNum 结构体指针，以便访问结构体的成员。
• 返回值：return ((struct phoneNum *)a)->num > ((struct phoneNum *)b)->num; 表达式用于比较两个 phoneNum 结构体的 num 字段，决定排序顺序。

学习重点：

• Lambda 表达式：C++11 引入了 lambda 表达式，使得函数的定义和使用更加灵活和简洁。在这里，它简化了 qsort 的比较函数编写。
• qsort 排序机制：理解 qsort 的工作原理，特别是如何通过自定义比较函数来实现不同的排序规则。

2. 哈希表的应用

哈希表是用于存储和快速查找数据的结构。它的核心思想是通过哈希函数将数据映射到一个特定的位置，以实现快速的插入和查找操作。在这段代码中，哈希表 storage 用来记录电话号码是否已经出现过。

unsigned char storage[250010] = {0}; // 哈希表

哈希表的实现细节：

• 位操作：程序使用位操作来标记电话号码是否出现过。每个电话号码都被映射到 storage 数组的特定位上。
• 哈希函数：通过计算 initNum 和 tailNum 的哈希值，确定该电话号码应该在 storage 数组的哪个位置。具体操作如下：

int stat(int initNum, int tailNum) {
    int a = (initNum / 3 - 1) * 125000 + tailNum / 8;
    int b = tailNum % 8;
    if (((storage[a] >> b) & 1) == 1) return 1;
    storage[a] = storage[a] | (1 << b);
    return 0;
}

• 哈希冲突：在这种简单的实现中，哈希冲突问题被通过位图的方法处理，每个位置（bit）仅表示某个号码是否出现过。

学习重点：

• 位操作的使用：位操作在哈希表中用于高效地存储和判断数据状态。这种方法节省了内存，并加快了判断速度。
• 哈希函数的设计：根据数据的特点设计合适的哈希函数，确保哈希表的效率。这里通过分割和组合号码来计算哈希值。

总结

通过这道题，你掌握了以下两个关键知识：

• qsort 的比较函数写法：特别是利用 C++11 的 lambda 表达式，可以简化代码，提高开发效率。
• 哈希表与位操作：理解了如何利用哈希表和位操作来实现高效的数据存储和查找，这是处理大规模数据的重要技术。

这两个知识点不仅有助于解决本题，还为你在处理类似问题时提供了有力的工具。掌握这些知识，能够让你更高效地编写和优化代码。