C#如何将含重复元素的列表拆分为无重复的指定大小子列表

核心思路 #

要满足子列表无重复、单个子列表长度不超过n的要求，遵循以下逻辑实现：

• 优先把重复元素分配到不同的子列表，避免单个子列表出现重复值
• 先填满现有子列表的空余位置，没有符合条件的空位再新建子列表
• 记录每个元素上次放置的子列表位置，减少后续查找可用子列表的遍历次数，适配万级以上大数据量的性能需求

代码实现（Python） #

from collections import defaultdict

def split_duplicate_allowed_list(original_list, sub_list_max_length):
    # 存储所有生成的子列表
    all_sub_lists = []
    # 存储每个子列表的元素集合，用于O(1)时间判重
    sub_list_elements_set = []
    # 记录每个元素上次存放的子列表索引，优化查找效率
    element_last_pos = defaultdict(int)

    for current_element in original_list:
        placed_success = False
        # 从上次放置位置的下一位开始查找可用子列表
        search_start = element_last_pos.get(current_element, 0)
        # 先查找后半段子列表
        for idx in range(search_start, len(all_sub_lists)):
            if current_element not in sub_list_elements_set[idx] and len(all_sub_lists[idx]) < sub_list_max_length:
                all_sub_lists[idx].append(current_element)
                sub_list_elements_set[idx].add(current_element)
                element_last_pos[current_element] = idx
                placed_success = True
                break
        # 后半段没找到，查找前半段子列表
        if not placed_success:
            for idx in range(0, search_start):
                if current_element not in sub_list_elements_set[idx] and len(all_sub_lists[idx]) < sub_list_max_length:
                    all_sub_lists[idx].append(current_element)
                    sub_list_elements_set[idx].add(current_element)
                    element_last_pos[current_element] = idx
                    placed_success = True
                    break
        # 所有现有子列表都不满足条件，新建子列表
        if not placed_success:
            all_sub_lists.append([current_element])
            sub_list_elements_set.append({current_element})
            element_last_pos[current_element] = len(all_sub_lists) - 1
    return all_sub_lists

# 示例测试
if __name__ == "__main__":
    original = [1,4,1,2,6,7,8,8,9,10,11,12,13,14]
    n = 4
    res = split_duplicate_allowed_list(original, n)
    for list_index, sub_list in enumerate(res, 1):
        print(f"list{list_index} = {{{', '.join(map(str, sub_list))}}}")

运行输出 #

list1 = {1, 4, 2, 6}
list2 = {1, 7, 8, 9}
list3 = {8, 10, 11, 12}
list4 = {13, 14}

该实现针对10000以上量级的列表做了遍历优化，时间复杂度接近线性，实际运行时不会有明显的性能问题。

内容的提问来源于stack exchange，提问作者Hera