mode_sorted.js

/**
 * [众数](https://en.wikipedia.org/wiki/Mode_%28statistics%29)是数据集中出现次数最多的数值。
 * 一个数据集可能存在多个众数：当出现频率相同的多个值时，本算法将返回最后出现的众数。
 * 这是[集中趋势的度量](https://en.wikipedia.org/wiki/Central_tendency)方法：
 * 用于寻找数据集的典型值或中心值。
 *
 * 由于输入已排序，算法时间复杂度为`O(n)`。
 *
 * @param {Array<number>} sorted 已排序的数据样本（需包含至少一个数据点）
 * @returns {number} 众数值
 * @throws {Error} 当输入为空时抛出错误
 * @example
 * modeSorted([0, 0, 1]); // => 0
 */
function modeSorted(sorted) {
    // 处理边界情况：
    // 空数组无众数定义
    if (sorted.length === 0) {
        throw new Error("计算众数需要至少一个数据点");
    }
    if (sorted.length === 1) {
        return sorted[0];
    }

    // 以下逻辑处理数组长度>1的情况，因此从索引1开始遍历
    let last = sorted[0];
    // 当前找到的众数值
    let value = Number.NaN;
    // 当前众数出现次数
    let maxSeen = 0;
    // 当前数值连续出现次数
    let seenThis = 1;

    // 遍历至sorted.length + 1以处理众数是最大元素的情况，
    // 最后一步将比较sorted[i]（此时为undefined）与最后一个元素
    for (let i = 1; i < sorted.length + 1; i++) {
        // 发现新数值时进行判断
        if (sorted[i] !== last) {
            // 若当前数值出现次数超过已知众数，则更新众数值
            if (seenThis > maxSeen) {
                maxSeen = seenThis;
                value = last;
            }
            seenThis = 1;
            last = sorted[i];
            // 相同数值则累加计数器
        } else {
            seenThis++;
        }
    }
    return value;
}

export default modeSorted;