题解 | #牛牛排队#

题意整理

给定一个环形数组，开始的时候，牛牛在起始位置。
每经过1分钟，环形数组中对应元素减去1，并且牛牛会沿着环形数组不断后移。
如果牛牛所在位置，元素值小于等于0，则返回对应位置下标。

方法一（模拟）

1.解题思路

用一个变量记录排队时间。
通过循环，模拟遍历环形数组，没执行一次，排队时间加一，如果对应下标元素值减去排队时间小于等于0，说明可以进入对应的门，直接返回。

测试数据较大的时候，运行超时。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回牛牛最终是从第几个门进入食堂吃饭的
     * @param n int整型 代表门的数量
     * @param a int整型一维数组 代表每个门外等待的人数
     * @return int整型
     */
    public int nowcoderQueue (int n, int[] a) {
        //记录排队时间
        int time=0;
        for(int i=0;i<n;i=(i+1)%n){
            //如果某个门排队人数小于等于0，说明可以进入，直接返回对应门的编号
            if(a[i]-time<=0){
                return i+1;
            }
            time++;
        }
        return -1;
    }
}

3.复杂度分析

时间复杂度：假设数组中最小值为min，最多需要循环 $min+n$ 次，所以时间复杂度为 $O(n+min)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。

方法二（预处理+模拟）

1.解题思路

简单分析：
由于每经过一圈，如果还不能进入到对应的门，牛牛都会回到起始位置。所以我们可以预先计算出最小值，如果最小值大于n，说明牛牛仍然会回到起始位置，没回到起始位置一次，数组中所有元素就要减去相应的排队时间n，所以直接减去n的倍数，直到最小值小于等于n。

基本步骤：

计算数组最小值。
对数组进行预处理，如果最小值大于n，所有元素减去n的倍数，直到最小值小于等于n。
按方法一的方式进行循环。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回牛牛最终是从第几个门进入食堂吃饭的
     * @param n int整型 代表门的数量
     * @param a int整型一维数组 代表每个门外等待的人数
     * @return int整型
     */
    public int nowcoderQueue (int n, int[] a) {
        //计算最小值
        int min=Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            min=Math.min(min,a[i]);
        }
        //如果最小值大于n，进行预处理
        if(min>n){
            int d=min/n*n;
            //将所有数减去n的倍数，直到最小值小于n
            for(int i=0;i<n;i++){
                a[i]-=d;
            }
        }
        //记录排队时间
        int time=0;
        for(int i=0;i<n;i=(i+1)%n){
            //如果某个门排队人数小于等于0，说明可以进入，直接返回对应门的编号
            if(a[i]-time<=0){
                return i+1;
            }
            time++;
        }
        return -1;
    }
}

3.复杂度分析

时间复杂度：假设数组中最小值为min，预处理之后，最多需要循环 $min\%n+n$ 次，所以时间复杂度为 $O(min\%n+n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。