What is the most efficient way to solve the "Assign Elements to Groups with Constraints" problem?

The most efficient way involves using array scanning combined with hash table lookups, possibly applying a sieve-like method to reduce redundant checks.

How do I handle cases where no element fits a group?

Return -1 for that group, indicating that no element could be assigned based on the group size constraint.

What is the time complexity of the solution?

The time complexity depends on the approach chosen, but it is typically linear with respect to the number of groups and elements, O(n + m), where n is the number of groups and m is the number of elements.

Can I optimize the solution further?

Yes, using a hash table for element lookups can significantly speed up the process, and applying a sieve-like filtering technique can reduce unnecessary operations.

What happens if elements are smaller than the group size?

If no element fits, the group should be assigned -1, meaning no suitable element is available for that group.

#3447

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

将元素分配给有约束条件的组

给你一个整数数组 groups ，其中 groups[i] 表示第 i 组的大小。另给你一个整数数组 elements 。请你根据以下规则为每个组分配一个元素：如果 groups[i] 能被 elements[j] 整除，则下标为 j 的元素可以分配给组 i 。如果有多个元素满足条件，则分…

数组哈希表

题目描述

给你一个整数数组 groups，其中 groups[i] 表示第 i 组的大小。另给你一个整数数组 elements。

请你根据以下规则为每个组分配一个元素：

如果 groups[i] 能被 elements[j] 整除，则下标为 j 的元素可以分配给组 i。
如果有多个元素满足条件，则分配 最小的下标 j 的元素。
如果没有元素满足条件，则分配 -1 。

返回一个整数数组 assigned，其中 assigned[i] 是分配给组 i 的元素的索引，若无合适的元素，则为 -1。

注意：一个元素可以分配给多个组。

示例 1：

输入： groups = [8,4,3,2,4], elements = [4,2]

输出： [0,0,-1,1,0]

解释：

elements[0] = 4 被分配给组 0、1 和 4。
elements[1] = 2 被分配给组 3。
无法为组 2 分配任何元素，分配 -1 。

示例 2：

输入： groups = [2,3,5,7], elements = [5,3,3]

输出： [-1,1,0,-1]

解释：

elements[1] = 3 被分配给组 1。
elements[0] = 5 被分配给组 2。
无法为组 0 和组 3 分配任何元素，分配 -1 。

示例 3：

输入： groups = [10,21,30,41], elements = [2,1]

输出： [0,1,0,1]

解释：

elements[0] = 2 被分配给所有偶数值的组，而 elements[1] = 1 被分配给所有奇数值的组。

提示：

1 <= groups.length <= 10⁵
1 <= elements.length <= 10⁵
1 <= groups[i] <= 10⁵
1 <= elements[i] <= 10⁵

lightbulb

解题思路

方法一：枚举

我们先找到数组 $\textit{groups}$ 中的最大值，记为 $\textit{mx}$ 。用一个数组 $\textit{d}$ 记录每个元素对应的下标，初始时 $\textit{d}[x] = -1$ 表示元素 $x$ 还没有被分配。

然后我们遍历数组 $\textit{elements}$ ，对于每个元素 $x$ ，如果 $x > \textit{mx}$ 或者 $\textit{d}[x] \neq -1$ ，说明元素 $x$ 无法被分配或者已经被分配，直接跳过。否则，我们从 $x$ 开始，每次加上 $x$ ，将 $\textit{d}[y]$ 设为 $j$ ，表示元素 $y$ 被分配给了下标 $j$ 。

最后我们遍历数组 $\textit{groups}$ ，根据 $\textit{d}$ 数组的记录，得到答案。

时间复杂度 $O(M \times \log m + n)$ ，空间复杂度 $O(M)$ 。其中 $n$ 和 $m$ 分别是数组 $\textit{groups}$ 和 $\textit{elements}$ 的长度；而 $M$ 是数组 $\textit{groups}$ 中的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def assignElements(self, groups: List[int], elements: List[int]) -> List[int]:
        mx = max(groups)
        d = [-1] * (mx + 1)
        for j, x in enumerate(elements):
            if x > mx or d[x] != -1:
                continue
            for y in range(x, mx + 1, x):
                if d[y] == -1:
                    d[y] = j
        return [d[x] for x in groups]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Test if the candidate can optimize array scanning with hashing.
question_mark
Look for understanding of sieve-like techniques applied to grouping problems.
question_mark
Assess if the candidate avoids redundant work by using appropriate data structures.

warning

常见陷阱

外企场景

error
Failing to use efficient data structures like hash tables leads to inefficient solutions.
error
Overlooking cases where no suitable element is available, leading to incorrect -1 assignments.
error
Not handling the edge cases where groups or elements are exhausted early.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the problem to require exact group size matching instead of any available element.
arrow_right_alt
Introduce additional constraints on elements, like limited reuse or an order of assignment.
arrow_right_alt
Allow multiple elements per group, adding complexity to the assignment logic.

help

常见问题

外企场景

继续练习

#3434 子数组操作后的最大频率 #3425 最长特殊路径 #3471 找出最大的几近缺失整数