LeetCode #2073 Time Needed to Buy Tickets 買到票所需要的時間

英文原文如下

There are n people in a line queuing to buy tickets, where the 0^th person is at the front of the line and the (n – 1)^th person is at the back of the line.

You are given a 0-indexed integer array tickets of length n where the number of tickets that the i^th person would like to buy is tickets[i].

Each person takes exactly 1 second to buy a ticket. A person can only buy 1 ticket at a time and has to go back to the end of the line (which happens instantaneously) in order to buy more tickets. If a person does not have any tickets left to buy, the person will leave the line.

Return the time taken for the person at position k (0-indexed) to finish buying tickets.

中文翻譯

有 n 個人排成一行要買票，站在最前面的人是第 0 位人，而站在最後面的是第  (n – 1) 位人。 (順序從0開始，跟陣列相同)

給予你一個長度為 n 且從0開始的整數陣列 tickets ，其代表著每個人想買的票數 ( tickets[i] 就是第 i 位人要買的票數 )

每一個人需要花費一秒來買一張票，而且每個人一次只能買一張票，然後如果要買更多的票就要去隊伍的尾端重排(會在瞬間發生)。如果一個人需要的票都買完了，他/她就會離開排隊隊伍。

回傳位置為  k (從0開始)的人買完全部他/她所需的票要多久。

範例及題目限制

Example 1:

Input: tickets = [2,3,2], k = 2
Output: 6
Explanation: 
- In the first pass, everyone in the line buys a ticket and the line becomes [1, 2, 1].
- In the second pass, everyone in the line buys a ticket and the line becomes [0, 1, 0].
The person at position 2 has successfully bought 2 tickets and it took 3 + 3 = 6 seconds.

Example 2:

Input: tickets = [5,1,1,1], k = 0
Output: 8
Explanation:
- In the first pass, everyone in the line buys a ticket and the line becomes [4, 0, 0, 0].
- In the next 4 passes, only the person in position 0 is buying tickets.
The person at position 0 has successfully bought 5 tickets and it took 4 + 1 + 1 + 1 + 1 = 8 seconds.

Constraints:

• n == tickets.length
• 1 <= n <= 100
• 1 <= tickets[i] <= 100
• 0 <= k < n

解題思路

這一題當然可以用while迴圈來實際模擬狀況，但那樣也太久了

故，經過思考後，解法如下

以第k位的人做一個標準

• 在第k位以前的人，最多可以買到跟 tickets[k] 一樣
• 而在以後的人，最多也只能買到 tickets[k]-1 (因為計算時間最後會排到 k位結束)

故我們只需要用一次迴圈來判斷就好，大家能買到票的數量最多就是上述的這樣，但當然也可能有人在買到上限前就離開隊伍的~

C# 解決方案

方案1

public class Solution {
    public int TimeRequiredToBuy(int[] tickets, int k) {
        int max = tickets[k];
        int secs = 0;
        for(int i=0; i<tickets.Length; i++){
            var curr = tickets[i];
            if(i<=k){
                secs+=Math.Min(curr,max);
            }
            else{
                secs+=Math.Min(curr,max-1);
            }
        }

        return secs;
    }
}

時間複雜度 : O(n)

Java 解決方案

方案1

class Solution {
    public int timeRequiredToBuy(int[] tickets, int k) {
        int max = tickets[k];
        int secs = 0;
        for(int i=0; i<tickets.length; i++){
            int curr = tickets[i];
            if(i<=k){
                secs+=Math.min(curr,max);
            }
            else{
                secs+=Math.min(curr,max-1);
            }
        }

        return secs;
    }
}

時間複雜度 : O(n)

結論

要是演唱會的票都可以排隊買就好了… 前陣子不管是IU還是張學友的門票，一開賣網頁跑完就搶光了…

或許是時候寫個機器人搶票了?

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡收藏文章或幫我點個廣告，那都是對我的支持

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Time Needed to Buy Tickets – LeetCode

隨機掉落的LeetCode文章