Description: https://leetcode.com/problems/time-needed-to-buy-tickets/description/
Code: Time complexity O(n2)
public static int timeRequiredToBuy(int[] tickets, int k) { int count = 0; while (tickets[k] > 0) { for (int i=0;i<tickets.length;i++) if (tickets[i] > 0) { tickets[i]--; count++; if (tickets[k] == 0) return count; } } return count; }
Can be simplified to O(n) as we do not need to iterate every time to count the time.
public static int timeRequiredToBuy(int[] tickets, int k) { int time = 0; for (int i = 0; i < tickets.length; i++) { if (i <= k) { // 对于索引k及之前的人,我们取他们的票数与k的票数的较小值 time += Math.min(tickets[i], tickets[k]); } else { // 对于索引k之后的人,我们只需要考虑在k之前他们能买的票数 time += Math.min(tickets[i], tickets[k] - 1); } } return time; }