题目链接

买票需要的时间

题目描述

有 n 个人在一个队列里购买电影票，每个人要购买的票数由数组 tickets 表示，tickets[i] 是第 i 个人要买的票数。第 k 个人是你特别关心的人。

整个过程遵循以下规则：

  1. 每个人轮流从队首购买一张票，这个过程耗时 1 秒。
  2. 买完一张票后，如果这个人还需要购买更多的票，他会移动到队尾，重新排队。
  3. 如果这个人已经买完了他需要的所有票，他会离开队列。

你需要计算并返回第 k 个人买完他所有票总共需要的时间。

示例 输入: tickets = [1,1,4,5,1,4], k = 2 输出: 13

解题思路

虽然这个问题可以用一个队列来直接模拟，但这样做效率不高。一个更优的解法是直接通过一次遍历来计算总时间。

我们可以把总时间看作是所有人购买行为耗时的总和，直到第 k 个人完成任务为止。我们以第 k 个人需要购买的票数 tickets[k] 为基准，分析队列中每个人（包括他自己）会完整地排队多少轮。

  1. 对于排在第 k 个人前面的人（包括第 k 个人自己，即索引 i <= k）:

    • 在第 k 个人买完所有票之前，这些人至少会和第 k 个人一样，有机会排满 tickets[k] 轮。
    • 如果这个人 i 本身需要的票数 tickets[i] 少于 tickets[k]，那么他会在 tickets[i] 轮后提前离场。
    • 因此，这类人耗费的时间是 min(tickets[i], tickets[k]) 秒。

  2. 对于排在第 k 个人后面的人（即索引 i > k）:

    • 这些人总是比第 k 个人晚一步。当第 k 个人进行第 tickets[k] 轮购买并离场时，这一轮还没有轮到他们。
    • 所以，他们最多只会完整地排 tickets[k] - 1 轮。
    • 同样，如果他们自己需要的票数 tickets[i] 比 tickets[k] - 1 还少，他们会更早离场。
    • 因此，这类人耗费的时间是 min(tickets[i], tickets[k] - 1) 秒。

我们只需要遍历整个 tickets 数组，根据上述两种情况累加每个人的耗时，就能得到最终的总时间。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param tickets int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int timeRequiredToBuy(vector<int>& tickets, int k) {
        int time = 0;
        int n = tickets.size();
        for (int i = 0; i < n; ++i) {
            if (i <= k) {
                time += min(tickets[i], tickets[k]);
            } else {
                time += min(tickets[i], tickets[k] - 1);
            }
        }
        return time;
    }
};

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param tickets int整型一维数组
     * @param k int整型
     * @return int整型
     */
    public int timeRequiredToBuy(int[] tickets, int k) {
        int time = 0;
        int n = tickets.length;
        for (int i = 0; i < n; i++) {
            if (i <= k) {
                time += Math.min(tickets[i], tickets[k]);
            } else {
                time += Math.min(tickets[i], tickets[k] - 1);
            }
        }
        return time;
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param tickets int整型一维数组
# @param k int整型
# @return int整型
#
class Solution:
    def timeRequiredToBuy(self , tickets: List[int], k: int) -> int:
        time = 0
        n = len(tickets)
        for i in range(n):
            if i <= k:
                time += min(tickets[i], tickets[k])
            else:
                time += min(tickets[i], tickets[k] - 1)
        return time

算法及复杂度

  • 算法：单次遍历、数学计算
  • 时间复杂度：，其中 N 是 tickets 数组的长度，因为我们只需要遍历一次数组。
  • 空间复杂度：，我们没有使用额外的、随输入大小增长的存储空间。