跳转至

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

题目描述

给你一个整数数组 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 <= 105
  • 1 <= elements.length <= 105
  • 1 <= groups[i] <= 105
  • 1 <= elements[i] <= 105

解法

方法一：枚举

我们先找到数组 \(\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
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]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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]);
}

评论