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

来源第 436 场周赛 Q2难度中等分数1730

题目描述

给你一个整数数组 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⁵

解法

方法一：枚举

思考

每个 \(\textit{groups}[i]\) 要分到能整除它的、下标最小的 \(\textit{elements}[j]\)。若对每个组扫描全部元素，\(n,m\le 10^5\) 会超时。

值域 \(M\le 10^5\)，从因子去标记倍数，类似埃氏筛，每个数只被其因子更新一次。

按 \(\textit{elements}\) 从左到右，对尚未标记的 \(x\) 遍历 \(x,2x,\ldots\le M\)，把 \(\textit{d}[y]\) 写成当前下标。组的答案即 \(\textit{d}[\textit{groups}[i]]\)。重复因子跳过，避免后出现的更大下标覆盖。

我们先找到数组 \(\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}\) 中的最大值。

Python3JavaC++GoTypeScript

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]

class Solution {
    public int[] assignElements(int[] groups, int[] elements) {
        int mx = Arrays.stream(groups).max().getAsInt();
        int[] d = new int[mx + 1];
        Arrays.fill(d, -1);
        for (int j = 0; j < elements.length; ++j) {
            int x = elements[j];
            if (x > mx || d[x] != -1) {
                continue;
            }
            for (int y = x; y <= mx; y += x) {
                if (d[y] == -1) {
                    d[y] = j;
                }
            }
        }
        int n = groups.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = d[groups[i]];
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> assignElements(vector<int>& groups, vector<int>& elements) {
        int mx = ranges::max(groups);
        vector<int> d(mx + 1, -1);

        for (int j = 0; j < elements.size(); ++j) {
            int x = elements[j];
            if (x > mx || d[x] != -1) {
                continue;
            }
            for (int y = x; y <= mx; y += x) {
                if (d[y] == -1) {
                    d[y] = j;
                }
            }
        }

        vector<int> ans(groups.size());
        for (int i = 0; i < groups.size(); ++i) {
            ans[i] = d[groups[i]];
        }

        return ans;
    }
};

func assignElements(groups []int, elements []int) (ans []int) {
    mx := slices.Max(groups)
    d := make([]int, mx+1)
    for i := range d {
        d[i] = -1
    }
    for j, x := range elements {
        if x > mx || d[x] != -1 {
            continue
        }
        for y := x; y <= mx; y += x {
            if d[y] == -1 {
                d[y] = j
            }
        }
    }
    for _, x := range groups {
        ans = append(ans, d[x])
    }
    return
}

function assignElements(groups: number[], elements: number[]): number[] {
    const mx = Math.max(...groups);
    const d: number[] = Array(mx + 1).fill(-1);
    for (let j = 0; j < elements.length; ++j) {
        const x = elements[j];
        if (x > mx || d[x] !== -1) {
            continue;
        }
        for (let y = x; y <= mx; y += x) {
            if (d[y] === -1) {
                d[y] = j;
            }
        }
    }
    return groups.map(x => d[x]);
}

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

题目描述

解法

方法一：枚举

评论