题解 | #队列消数#
队列消数
https://www.nowcoder.com/practice/48f6e451ff52440798067b77dc5ea95b
题目链接
题目描述
有 n 个人在一个队列里购买电影票，每个人要购买的票数由数组 tickets 表示，tickets[i] 是第 i 个人要买的票数。第 k 个人是你特别关心的人。
整个过程遵循以下规则：
- 每个人轮流从队首购买一张票，这个过程耗时 1 秒。
- 买完一张票后，如果这个人还需要购买更多的票，他会移动到队尾，重新排队。
- 如果这个人已经买完了他需要的所有票，他会离开队列。
你需要计算并返回第 k 个人买完他所有票总共需要的时间。
示例
输入: tickets = [1,1,4,5,1,4], k = 2
输出: 13
解题思路
虽然这个问题可以用一个队列来直接模拟，但这样做效率不高。一个更优的解法是直接通过一次遍历来计算总时间。
我们可以把总时间看作是所有人购买行为耗时的总和，直到第 k 个人完成任务为止。我们以第 k 个人需要购买的票数 tickets[k] 为基准，分析队列中每个人（包括他自己）会完整地排队多少轮。
-
对于排在第
k个人前面的人（包括第k个人自己，即索引i <= k）:- 在第
k个人买完所有票之前，这些人至少会和第k个人一样，有机会排满tickets[k]轮。 - 如果这个人
i本身需要的票数tickets[i]少于tickets[k]，那么他会在tickets[i]轮后提前离场。 - 因此，这类人耗费的时间是
min(tickets[i], tickets[k])秒。
- 在第
-
对于排在第
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数组的长度，因为我们只需要遍历一次数组。 - 空间复杂度：
，我们没有使用额外的、随输入大小增长的存储空间。
查看18道真题和解析