题解 | #排队购票#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numTickets int整型
     * @param visitorTimes int整型一维数组
     * @return int整型一维数组
     */
  /**
  方法一：时间复杂度:O(n2)
  */
     public  int[] ticketQueue(int numTickets, int[] visitorTimes) {
        List<Integer[]> res = new ArrayList<>();
        int n = visitorTimes.length;
        for (int i = 0; i < n; i++) {
            res.add(new Integer[]{visitorTimes[i], i + 1});
        }
        res.sort(Comparator.comparingInt(a -> a[0]));
        int[] ans = new int[numTickets];
        for (int i = 0; i < numTickets; i++) {
            ans[i] = res.get(i)[1];
        }
        return ans;
    }
  /**
  方法二: 时间复杂度O(nlogn)但是耗时120+ms,估计是res.sort极大增加了耗时
  */
      public  int[] ticketQueue(int numTickets, int[] visitorTimes) {
        List<Integer[]> res = new ArrayList<>();
        int n = visitorTimes.length;
        for (int i = 0; i < n; i++) {
            res.add(new Integer[]{visitorTimes[i], i + 1});
        }
        res.sort(Comparator.comparingInt(a -> a[0]));
        int[] ans = new int[numTickets];
        for (int i = 0; i < numTickets; i++) {
            ans[i] = res.get(i)[1];
        }
        return ans;
    }
}

本题知识点分析：

1.队列

2.有序集合存取

3.API函数排序

4.数学模拟

本题解题思路分析：

1.方法一就是拷贝一份原数组，然后排序，然后根据这个值去找原数组的索引位置，当找到后赋值为0，是为了防止出现相同的数，出现错误情况，比如用例：2 {1,1}，要是不赋值为0，就会出现，答案是{1,1}，其实答案是{1,2}

2.方法二时间复杂度是O(nlogn)比方法一低，但是耗时却增加了100多ms,估计是res.sort这里的快速排序没有手写的缘故

3.如果使用队列的话其实是一样的，一个优先级队列存放时间，一个存放用户编号，然后就是for循环去比较判断

本题使用编程语言: Java

如果你觉得对你有帮助的话，可以点个赞，感谢~