题目链接

无法吃午餐的学生数量

题目描述

给定代表学生偏好（0代表喜欢圆形，1代表喜欢方形）的整数序列 students，和代表三明治类型（0为圆形，1为方形）的整数序列 sandwiches。students 序列视为一个队列，sandwiches 序列视为一个栈。

模拟以下过程：

  1. 队首的学生查看栈顶的三明治。
  2. 如果学生喜欢这个三明治（偏好与三明治类型相同），他将取走三明治，然后离开队列。
  3. 如果学生不喜欢，他会回到队列的末尾。
  4. 这个过程持续进行，直到队列中剩下的所有学生都不喜欢栈顶的三明治为止。

你需要返回最终无法吃到午餐的学生数量。

示例 输入: students = [1,1,0,1], sandwiches = [1,0,0,1] 输出: 2

解题思路

虽然题目描述了一个队列和栈的模拟过程，但直接模拟会导致在学生不喜欢三明治时，需要将学生从队首移到队尾，效率不高。

一个更高效的解法是计数法。核心思想是：学生在队列里的顺序其实不重要，重要的是还剩下多少个喜欢圆形三明治的学生，以及多少个喜欢方形的。

  1. 统计学生偏好：首先遍历 students 数组，统计喜欢圆形（0）和方形（1）三明治的学生各有多少人。我们可以用一个数组 counts 来存放，counts[0] 是喜欢圆形的人数，counts[1] 是喜欢方形的人数。

  2. 分发三明治：接着，我们从头到尾遍历 sandwiches 数组，这个过程相当于模拟三明治出栈。

    • 对于每一个三明治 s，我们检查是否还有喜欢这种三明治的学生（即 counts[s] > 0）。
    • 如果有，说明这个三明治可以被一个学生取走，我们将对应的学生计数减一（counts[s]--）。
    • 如果counts[s] == 0，这意味着已经没有学生喜欢这种类型的三明治了。此时，队列中剩下的所有学生都永远无法匹配到这个栈顶的三明治，他们将无限循环下去。因此，模拟过程结束。

  3. 计算剩余学生：当循环因为上述情况而中断时，队列中剩余的学生总数就是 counts[0] + counts[1]，也就是最终无法吃到午餐的学生数量。如果循环正常结束（所有三明治都被取走），那么剩余学生为0。

这个方法避免了复杂的队列操作，将时间复杂度从可能最坏的 优化到了 。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param students int整型vector 
     * @param sandwiches int整型vector 
     * @return int整型
     */
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        int counts[2] = {0, 0};
        for (int student : students) {
            counts[student]++;
        }

        for (int sandwich : sandwiches) {
            if (counts[sandwich] > 0) {
                counts[sandwich]--;
            } else {
                // No student wants this sandwich, process stops.
                break;
            }
        }

        return counts[0] + counts[1];
    }
};

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param students int整型一维数组
     * @param sandwiches int整型一维数组
     * @return int整型
     */
    public int countStudents(int[] students, int[] sandwiches) {
        int[] counts = new int[2];
        for (int student : students) {
            counts[student]++;
        }

        for (int sandwich : sandwiches) {
            if (counts[sandwich] > 0) {
                counts[sandwich]--;
            } else {
                break;
            }
        }

        return counts[0] + counts[1];
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param students int整型一维数组
# @param sandwiches int整型一维数组
# @return int整型
#
class Solution:
    def countStudents(self , students: List[int], sandwiches: List[int]) -> int:
        counts = [0, 0]
        for student in students:
            counts[student] += 1
        
        for sandwich in sandwiches:
            if counts[sandwich] > 0:
                counts[sandwich] -= 1
            else:
                break
        
        return counts[0] + counts[1]

算法及复杂度

  • 算法：计数、贪心
  • 时间复杂度：，其中 N 是学生数量，M 是三明治数量。我们需要分别遍历一次学生和三明治数组。因为 N=M，所以是 。
  • 空间复杂度：，我们只需要一个固定大小的数组来存储两种偏好的学生数量。