AC110-三递增序列公共元素查找

代码实现

// 函数 fmax：返回三个整数中的最大值
int fmax(int a, int b, int c) {
    if (a > b && a > c) {
        return a; // 如果 a 是最大的，则返回 a
    } else if (b > a && b > c) {
        return b; // 如果 b 是最大的，则返回 b
    } else {
        return c; // 否则返回 c
    }
}

// 函数 samekey：输出三个递增序列中共同存在的所有元素
void samekey(int A[], int B[], int C[], int n) {
    int i = 0, j = 0, k = 0; // 初始化三个指针，分别指向 A、B、C 的起始位置

    // 循环条件：三个指针均未超出数组范围
    while (i < n && j < n && k < n) {
        // 如果当前三个指针指向的元素相等，则该元素是公共元素
        if (A[i] == B[j] && A[i] == C[k]) {
            printf("%d ", A[i]); // 输出公共元素
            i++; // 移动指针 i 到下一个位置
            j++; // 移动指针 j 到下一个位置
            k++; // 移动指针 k 到下一个位置
        } else {
            // 找到当前三个指针指向的元素中的最大值
            int max_num = fmax(A[i], B[j], C[k]);

            // 将指向较小元素的指针向前移动，以缩小差距
            if (A[i] < max_num) {
                i++; // 如果 A[i] 小于最大值，则移动指针 i
            }
            if (B[j] < max_num) {
                j++; // 如果 B[j] 小于最大值，则移动指针 j
            }
            if (C[k] < max_num) {
                k++; // 如果 C[k] 小于最大值，则移动指针 k
            }
        }
    }
}

---

代码逻辑解析

1. 初始化指针：
2. i, j, k 分别指向数组 A, B, C 的起始位置（即索引为 0 的位置）。

3. 这些指针用于遍历各自的数组。

4. 循环条件：

5. 当三个指针均未超出数组范围时，继续执行循环。

6. 判断是否找到公共元素：

7. 如果 A[i] == B[j] && A[i] == C[k]，说明当前三个指针指向的元素相同，这是一个公共元素。

8. 输出该公共元素后，将三个指针同时向后移动一位。

9. 未找到公共元素时的处理：

10. 调用 fmax 函数，找到当前三个指针指向的元素中的最大值 max_num。
11. 对于每个数组，如果其当前指针指向的元素小于 max_num，则将该指针向前移动一位。
12. 这样可以逐步使三个指针指向更接近的值，从而提高效率。

---

时间复杂度分析

• 循环次数：
• 每次循环至少会移动一个指针，因此总的循环次数最多为 3n（每个指针最多移动 n 次）。

• 因此，时间复杂度为 O(n)。

• 函数调用：

• fmax 函数的时间复杂度为 O(1)，因为它只涉及简单的比较操作。
• 整体来看，fmax 的调用不会显著增加时间复杂度。

综上，算法的时间复杂度为 O(n)。

---

空间复杂度分析

• 该算法只使用了常量级别的额外空间（如变量 i, j, k, max_num），没有使用与输入规模相关的额外空间。
• 因此，空间复杂度为 O(1)。

---

较难理解部分的说明

为什么每次只需要移动指向较小元素的指针？

• 由于三个数组均为无重复元素的递增序列，因此如果某个指针指向的元素小于其他两个指针指向的元素，那么它不可能是公共元素。
• 通过移动指向较小元素的指针，可以使三个指针更快地靠近潜在的公共元素，从而提高效率。

图解说明

假设三个数组如下：

A = [1, 3, 5, 7]
B = [2, 3, 6, 8]
C = [3, 4, 5, 9]

初始状态：

i -> A[0] = 1
j -> B[0] = 2
k -> C[0] = 3

• 第一次循环：max_num = 3，移动 i 和 j。
• 第二次循环：max_num = 3，此时 A[i] == B[j] == C[k]，输出 3，并移动 i, j, k。

最终输出结果为 3。

---

延伸知识点

1. 多指针法的应用：
2. 多指针法常用于解决多个有序数组的问题，例如查找交集、合并排序等。

3. 其核心思想是利用数组的有序性，通过移动指针快速缩小搜索范围。

4. 边界条件的处理：

5. 在实际应用中，需要特别注意数组为空或长度不一致的情况。

6. 此外，还需考虑是否存在重复元素的场景。

7. 扩展问题：

8. 如果数组不是严格递增的（允许重复元素），如何修改算法？
9. 如果有更多数组（如四个或五个），如何推广该算法？