AC105-从有序顺序表中找出出现次数最多的元素及对应次数，若有多个出现次数最多的元素，优先选取值最小的元素¶

实现代码¶

C
/**
 * 从有序顺序表中找出出现次数最多的元素及对应次数
 * 若有多个出现次数最多的元素，优先选取值最小的元素
 * @param L 顺序表（按值有序排列）
 */
void find(Sqlist L) {
    // 边界检查：空表情况
    if (L.length <= 0) {
        printf("顺序表为空\n");
        return;
    }

    int max_count = 1;      // 最大出现次数，初始为1
    int max_val = L.data[0]; // 出现次数最多的元素值，初始为第一个元素
    int count = 1;          // 当前元素的出现次数

    // 遍历顺序表，统计每个元素的出现次数
    for (int i = 0; i < L.length - 1; i++) {
        // 如果当前元素与下一个元素相同，计数加1
        if (L.data[i] == L.data[i + 1]) {
            count++;
        } else {
            // 当前元素序列结束，检查是否为最大次数
            if (count > max_count) { //这里已经隐含了“若有多个出现次数最多的元素，优先选取值最小的元素”，因为这里指明“严格大于”，出现次数与当前最值相等的元素必定较大。
                max_count = count;  // 更新最大次数
                max_val = L.data[i]; // 更新对应元素值
            }
            count = 1;  // 重置计数器，开始统计下一个元素
        }
    }

    // 处理最后一个元素序列（循环结束后还需要检查一次）
    if (count > max_count) {
        max_count = count;
        max_val = L.data[i];
    }

    // 输出结果
    printf("出现次数最多的元素为: %d\n", max_val);
    printf("最大出现次数为: %d\n", max_count);
}

算法执行过程图解¶

假设顺序表为：[1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5]

Text Only

初始状态:
数组: [1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5]
      ↑
      i=0
max_count=1, max_val=1, count=1

i=0: 1≠2 → count=1, 检查count<=max_count, 不更新
     max_count=1, max_val=1

i=1: 2=2 → count=2

i=2: 2≠3 → count=2, 检查count>max_count, 更新
     max_count=2, max_val=2
     count=1

i=3: 3=3 → count=2

i=4: 3=3 → count=3

i=5: 3≠4 → count=3, 检查count>max_count, 更新
     max_count=3, max_val=3
     count=1

i=6: 4≠5 → count=1, 检查count<=max_count, 不更新
     max_count=3, max_val=3
     count=1

i=7: 5=5 → count=2

i=8: 5=5 → count=3

i=9: 5=5 → count=4

循环结束后的最终检查:
count=4 > max_count=3 → 更新
max_count=4, max_val=5

最终结果: 元素5出现4次，为出现次数最多的元素

复杂度分析¶

时间复杂度：O(n)¶

详细分析：

遍历次数：
只需一次从左到右的线性扫描
每个元素最多访问一次
操作次数：
每次比较和计数操作都是常数时间
总操作次数与元素数量成正比
时间复杂度：O(n)

空间复杂度：O(1)¶

只使用了常数个额外变量（max_count, max_val, count, i）
没有使用额外的存储空间
空间复杂度为 O(1)

关键知识点延伸¶

1. 算法核心思想¶

利用有序性统计频次¶

由于数组已排序，相同元素必定相邻
可以通过一次扫描统计每个元素的连续出现次数
无需额外的数据结构存储统计信息

双指针技巧的变体¶

不需要显式的双指针
通过索引i和计数器count实现类似效果
count记录当前连续相同元素的个数

2. 特殊情况处理¶

2.1 空表或单元素表¶

C
// 空表处理
if (L.length <= 0) {
    printf("顺序表为空\n");
    return;
}

// 单元素表
// max_count=1, max_val=L.data[0] 直接就是结果

2.2 所有元素都相同¶

C
1 2	`// 输入: [5, 5, 5, 5, 5] // 输出: 元素5出现5次`

2.3 所有元素都不同¶

C
1 2	`// 输入: [1, 2, 3, 4, 5] // 输出: 元素1出现1次（优先选取值最小的）`

3. 多个最大次数元素的处理¶

题目要求："若有多个出现次数最多的元素，优先选取值最小的元素"

C
// 关键在于比较条件
if (count > max_count) {  // 只有严格大于时才更新
    max_count = count;
    max_val = L.data[i];
}
// 相等时不更新，保证保留值最小的元素

4. 优化实现版本¶

C
/**
 * 优化版本：更清晰的逻辑结构
 */
void findOptimized(Sqlist L) {
    if (L.length <= 0) {
        printf("顺序表为空\n");
        return;
    }

    int max_count = 0;      // 最大出现次数
    int max_val = L.data[0]; // 对应元素值

    int i = 0;
    while (i < L.length) {
        int current_val = L.data[i];
        int count = 0;

        // 统计当前元素的出现次数
        while (i < L.length && L.data[i] == current_val) {
            count++;
            i++;
        }

        // 更新最大次数和对应元素
        if (count > max_count) {
            max_count = count;
            max_val = current_val;
        }
    }

    printf("出现次数最多的元素为: %d\n", max_val);
    printf("最大出现次数为: %d\n", max_count);
}

5. 扩展应用¶

5.1 返回所有出现次数最多的元素¶

C
/**
 * 找出所有出现次数最多的元素
 */
void findAllMaxElements(Sqlist L) {
    if (L.length <= 0) return;

    int max_count = 0;

    // 第一次遍历：找出最大出现次数
    int i = 0;
    while (i < L.length) {
        int count = 1;
        while (i + count < L.length && L.data[i] == L.data[i + count]) {
            count++;
        }
        if (count > max_count) max_count = count;
        i += count;
    }

    // 第二次遍历：输出所有具有最大出现次数的元素
    i = 0;
    printf("出现次数最多的元素有: ");
    while (i < L.length) {
        int current_val = L.data[i];
        int count = 0;
        while (i < L.length && L.data[i] == current_val) {
            count++;
            i++;
        }
        if (count == max_count) {
            printf("%d ", current_val);
        }
    }
    printf("\n最大出现次数为: %d\n", max_count);
}

5.2 统计所有元素的出现次数¶

C
/**
 * 统计所有元素的出现次数
 */
void countAllElements(Sqlist L) {
    if (L.length <= 0) return;

    int i = 0;
    printf("元素出现次数统计:\n");

    while (i < L.length) {
        int current_val = L.data[i];
        int count = 0;

        // 统计当前元素出现次数
        while (i < L.length && L.data[i] == current_val) {
            count++;
            i++;
        }

        printf("元素 %d 出现 %d 次\n", current_val, count);
    }
}

6. 与无序表的对比¶

特性	有序表查找	无序表查找
时间复杂度	O(n)	O(n)（需要哈希表）或 O(n²)（暴力统计）
空间复杂度	O(1)	O(n)（需要哈希表存储）
实现难度	简单	中等
适用场景	已排序数据	任意顺序数据

算法特点总结¶

高效性：时间复杂度O(n)，空间复杂度O(1)
利用有序性：充分利用输入数据的有序特性
一次遍历：只需要扫描数组一次
原地操作：不需要额外存储空间
正确性保证：正确处理边界情况和特殊输入

记忆要点¶

有序性利用：相同元素相邻，可连续统计
边界处理：注意循环结束后的最后一次检查
优先级保证：相等时不更新，确保值最小的元素被选中
时间效率：线性时间O(n)，最优解
空间效率：原地操作O(1)，空间最优