题目描述

有 n 个人前来排队买票，其中第 0 人站在队伍最前方，第 n-1 人站在队伍最后方。给定一个整数数组 tickets，其中 tickets[i] 表示第 i 个人想要购买的票数。每个人买票需要 1 秒。一个人一次只能买一张票，买完后如果还需要买更多票，就必须走到队尾重新排队。返回位于位置 k 的人完成买票所需的时间。

例如：tickets = [2,3,2]，k = 2，输出 6。

解释：排队的模拟过程为：

  • 第 1 秒：第 0 人买一张，剩余 [1,3,2]，到队尾。
  • 第 2 秒：第 1 人买一张，剩余 [1,2,2]，到队尾。
  • 第 3 秒：第 2 人（k=2）买一张，剩余 [1,2,1]，到队尾。
  • 第 4 秒：第 0 人买一张，剩余 [0,2,1]，离队。
  • 第 5 秒：第 1 人买一张，剩余 [0,1,1]，到队尾。
  • 第 6 秒：第 2 人买最后一张，剩余 [0,1,0]，完成。所需时间为 6 秒。

解题思路

模拟法（代码所用方法）

直接按照题目描述的规则进行模拟。

步骤

  1. 初始化计数器 ans = 0，使用无限循环和取模运算模拟环形队列。
  2. 在循环中 index = i % tickets.length 获取当前买票人的下标：
    • 如果该人还需要买票（tickets[index] > 0）：
      • 检查：如果当前买票人恰好是 k 且这是他最后一张票（tickets[k] == 1），那么这次买票就是他完成的时刻，返回 ++ans。
      • 否则：ans++，tickets[index]--（买一张票）。
  3. 循环直到 k 位置的人完成买票。
  4. 返回 ans。

数学法（更优解法）

实际上这题有 O(n) 的数学解法。对于位置 k 的人：

  • 在他前面的人（i < k）最多买 min(tickets[i], tickets[k]) 张票。
  • 在他后面的人（i > k）最多买 min(tickets[i], tickets[k] - 1) 张票（因为最后一轮在 k 完成之后才轮到他后面的人）。

总时间 = 遍历所有人累加上述值即可。但模拟法更直观易懂。

示例说明

以模拟法说明（见题目描述），此处不再赘述。

复杂度分析

  • 时间复杂度：O(m * n)，其中 m 为最大票数，n 为人数。最坏情况下所有票数之和很大。
  • 空间复杂度：O(1)，只使用常数额外空间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package code.J2073;

public class J2073 {
    public int timeRequiredToBuy(int[] tickets, int k) {
        int ans = 0;
        for (int i = 0;true;i++){
            int index = i%tickets.length;
            if (tickets[index]>0){
                if (index == k && tickets[k] == 1) return ++ans;
                ans++;
                tickets[index]--;
            }
        }
    }
}