免单统计 - 华为OD机试真题(JavaScript题解)

华为OD机试题库《C++》限时优惠 9.9

华为OD机试题库《Python》限时优惠 9.9

华为OD机试题库《JavaScript》限时优惠 9.9

针对刷题难，效率慢，我们提供一对一算法辅导， 针对个人情况定制化的提高计划（全称1V1效率更高）。

看不懂有疑问需要答疑辅导欢迎私VX： code5bug

题目描述

华为商城举办了一个促销活动，如果某顾客是某一秒内最早时刻下单的顾客（可能是多个人），则可以获取免单。

请你编程计算有多少顾客可以获取免单。

输入描述

输入为 n 行数据，每一行表示一位顾客的下单时间

以（年-月-日时-分-秒.毫秒） yyyy-MM-ddHH:mm:ss.fff 形式给出。

• 0<n<50000
• 2000<yyyy<2020
• 0<MM<=12
• 0<dd<=28
• 0<=HH<=23
• 0<=mm<=59
• 0<=ss<=59
• 0<=fff<=999

所有输入保证合法。

输出描述

输出一个整数，表示有多少顾客可以获取免单。

示例1

输入：
3
2019-01-01 00:00:00.001
2019-01-01 00:00:00.002
2019-01-01 00:00:00.003

输出：
1

说明：
三个订单都是同一秒内下单，只有第一个订单最早下单，可以免单。

示例2

输入：
3
2019-01-01 08:59:00.123
2019-01-01 08:59:00.123
2018-12-28 10:08:00.999

输出：
3

说明：
前两个订单是同一秒内同一时刻（也是最早）下单，都可免单，第三个订单是当前秒内唯一一个订单（也是最早），也可免单。

示例3

输入：
5
2019-01-01 00:00:00.004
2019-01-01 00:00:00.004
2019-01-01 00:00:01.006
2019-01-01 00:00:01.006
2019-01-01 00:00:01.005

输出：
3

说明：
前两个订单是同一秒内同一时刻（也是最早）下单，第三第四个订单不是当前秒内最早下单，不可免单，第五个订单可以免单。

题解

这道题目属于哈希表应用类问题，主要考察对时间数据的处理和高效查找能力。虽然题目描述涉及时间比较，但核心是通过哈希表来记录和维护每一秒内的最早下单时间及其出现次数。

解题思路

1. 问题分析：需要找出每一秒内最早下单的顾客（可能有多个相同的最早时间），统计这些顾客的总数。
2. 关键步骤：
   • 将每个时间戳按秒分组（忽略毫秒部分）
   • 对每一秒内的所有时间，找出最早的时间
   • 统计这些最早时间出现的总次数
3. 数据结构选择：使用哈希表（字典）来记录每一秒对应的最早时间和出现次数，可以高效地进行查找和更新。

时间复杂度

• 时间复杂度：O(n)

空间复杂度

• 空间复杂度：O(n)

JavaScript

const rl = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout,
});

var iter = rl[Symbol.asyncIterator]();

const readline = async () => (await iter.next()).value;

// Author: code5bug
(async () => {
    const n = parseInt(await readline());
    const times = [];
    for (let i = 0; i < n; i++) {
        times.push(await readline());
    }

    // 记录每一秒的最早时刻及其出现次数
    const start_time = new Map();
    for (let time of times) {
        // 分割出秒级部分作为键
        let second = time.split('.')[0];

        // 如果该秒还没有记录，或者当前时间更早，则更新
        if (!start_time.has(second) || time < start_time.get(second).time) {
            start_time.set(second, { time, count: 1 });
        } else if (time === start_time.get(second).time) {
            // 如果当前时间与记录的最早时间相同，则增加计数
            start_time.get(second).count++;
        }
    }

    // 统计免单单数
    const result = start_time.values().reduce((sum, cur) => sum + cur.count, 0);
    console.log(result);

    rl.close();
})();

希望这个专栏能让您熟练掌握算法, 🎁🎁🎁。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏