Medium

题目描述

给你一个整数数组 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 无法分配任何元素。

示例 2：

输入：groups = [2,3,5,7], elements = [5,3,3]
输出：[-1,1,0,-1]
解释：
- elements[1] = 3 分配给组 1。
- elements[0] = 5 分配给组 2。
- 组 0 和 3 无法分配任何元素。

示例 3：

输入：groups = [10,21,30,41], elements = [2,1]
输出：[0,1,0,1]
解释：
elements[0] = 2 分配给偶数值的组，elements[1] = 1 分配给奇数值的组。

约束条件：

  • 1 <= groups.length <= 10^5
  • 1 <= elements.length <= 10^5
  • 1 <= groups[i] <= 10^5
  • 1 <= elements[i] <= 10^5

解题思路

这道题需要为每个组找到能整除该组大小的最小索引元素。

思路分析：

  1. 朴素方法：对每个组遍历所有元素，找到第一个能整除的元素。时间复杂度为 O(n*m)，可能超时。

  2. 哈希表优化：使用哈希表记录每个元素值的最小索引，然后对每个组找其所有因子，选择索引最小的。

  3. 推荐解法 - 埃氏筛变形：从小索引开始，对于每个元素，找到所有它的倍数对应的组，并尝试更新这些组的分配结果。这样确保了索引小的元素优先被考虑。

具体步骤：

  • 初始化结果数组为 -1
  • 使用哈希表记录每个元素值的最小索引
  • 对于每个不同的元素值（按索引从小到大），遍历其所有倍数
  • 如果某个倍数是某个组的大小，且该组还未分配元素，则分配当前元素
  • 由于按索引顺序处理，自然保证了最小索引优先的要求

这种方法的优势是避免了对每个组都去找所有因子的重复计算，而是反向地从元素出发找能整除的组。

代码实现

class Solution {
public:
    vector<int> assignElements(vector<int>& groups, vector<int>& elements) {
        int n = groups.size();
        vector<int> assigned(n, -1);
        
        // 记录每个元素值的最小索引
        unordered_map<int, int> elementIndex;
        for (int i = 0; i < elements.size(); i++) {
            if (elementIndex.find(elements[i]) == elementIndex.end()) {
                elementIndex[elements[i]] = i;
            }
        }
        
        // 按索引排序元素
        vector<pair<int, int>> sortedElements; // {value, index}
        for (auto& p : elementIndex) {
            sortedElements.push_back({p.first, p.second});
        }
        sort(sortedElements.begin(), sortedElements.end(), 
             [](const pair<int,int>& a, const pair<int,int>& b) {
                 return a.second < b.second;
             });
        
        // 建立组大小到索引的映射
        unordered_map<int, vector<int>> groupMap;
        for (int i = 0; i < n; i++) {
            groupMap[groups[i]].push_back(i);
        }
        
        // 为每个元素找到它能整除的组
        for (auto& elem : sortedElements) {
            int value = elem.first;
            int index = elem.second;
            
            // 找到所有value的倍数
            for (int multiple = value; multiple <= 100000; multiple += value) {
                if (groupMap.count(multiple)) {
                    for (int groupIdx : groupMap[multiple]) {
                        if (assigned[groupIdx] == -1) {
                            assigned[groupIdx] = index;
                        }
                    }
                }
            }
        }
        
        return assigned;
    }
};

class Solution:
    def assignElements(self, groups: List[int], elements: List[int]) -> List[int]:
        n = len(groups)
        assigned = [-1] * n
        
        # 记录每个元素值的最小索引
        element_index = {}
        for i, elem in enumerate(elements):
            if elem not in element_index:
                element_index[elem] = i
        
        # 按索引排序元素
        sorted_elements = sorted(element_index.items(), key=lambda x: x[1])
        
        # 建立组大小到索引的映射
        group_map = {}
        for i, size in enumerate(groups):
            if size not in group_map:
                group_map[size] = []
            group_map[size].append(i)
        
        # 为每个元素找到它能整除的组
        for value, index in sorted_elements:
            # 找到所有value的倍数
            multiple = value
            while multiple <= 100000:
                if multiple in group_map:
                    for group_idx in group_map[multiple]:
                        if assigned[group_idx] == -1:
                            assigned[group_idx] = index
                multiple += value
        
        return assigned

public class Solution {
    public int[] AssignElements(int[] groups, int[] elements) {
        int n = groups.Length;
        int[] assigned = new int[n];
        Array.Fill(assigned, -1);
        
        // 记录每个元素值的最小索引
        Dictionary<int, int> elementIndex = new Dictionary<int, int>();
        for (int i = 0; i < elements.Length; i++) {
            if (!elementIndex.ContainsKey(elements[i])) {
                elementIndex[elements[i]] = i;
            }
        }
        
        // 按索引排序元素
        var sortedElements = elementIndex.OrderBy(p => p.Value).ToList();
        
        // 建立组大小到索引的映射
        Dictionary<int, List<int>> groupMap = new Dictionary<int, List<int>>();
        for (int i = 0; i < n; i++) {
            if (!groupMap.ContainsKey(groups[i])) {
                groupMap[groups[i]] = new List<int>();
            }
            groupMap[groups[i]].Add(i);
        }
        
        // 为每个元素找到它能整除的组
        foreach (var elem in sortedElements) {
            int value = elem.Key;
            int index = elem.Value;
            
            // 找到所有value的倍数
            for (int multiple = value; multiple <= 100000; multiple += value) {
                if (groupMap.ContainsKey(multiple)) {
                    foreach (int groupIdx in groupMap[multiple]) {
                        if (assigned[groupIdx] == -1) {
                            assigned[groupIdx] = index;
                        }
                    }
                }
            }
        }
        
        return assigned;
    }
}

var assignElements = function(groups, elements) {
    const assigned = new Array(groups.length);
    
    for (let i = 0; i < groups.length; i++) {
        assigned[i] = -1;
        for (let j = 0; j < elements.length; j++) {
            if (groups[i] % elements[j] === 0) {
                assigned[i] = j;
                break;
            }
        }
    }
    
    return assigned;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(M × MAX_VALUE / elements[i])，其中 M 是不同元素值的个数，MAX_VALUE = 10^5
空间复杂度O(N + M)，用于存储结果数组和哈希表映射