算法-找出N个数组的共同元素

一、代码与执行结果

财经新闻是大众了解金融事件的重要渠道,现有N位编辑,分别对K篇新闻进行专业的编辑与排版。需要您找出被这N位编辑共同编辑过的新闻,并根据这些新闻ID升序排列返回一个数组。

在这里插入图片描述

import random

# 查找编辑共同处理的新闻id
def find_common_news(N, K, news_ids):
    # 使用集合的交集操作找出被所有编辑共同编辑过的新闻
    common_news_set = set(news_ids[0]) # 时间 O(k)   # 空间 O(N)
    for i in range(1, N):  # O(N*K)
        common_news_set.intersection_update(news_ids[i]) 
    # 返回升序排列的结果
    return sorted(list(common_news_set)) # O(M * log(M)) 排序算法是 Timsort
    #  O(N * K + M * log(M))

# 生成模拟数据, 作为find_common_news的输入
def generate_random_lists(m=8, N=10, K=60):
    # 第1步:生成这些编辑们处理的新闻中一定重复的新闻id
    lists = random.sample(range(1, K+1), m)
    print('期望输出: ',sorted(lists)) 
    
    # 第2步:生成编辑们分别处理的新闻个数
    lsts2 = [random.randint(1, K) for _ in range(N)]
    # print(lsts2)

    # 第3步:生成这8个编辑各自处理的新闻中可能不重复的新闻id
    result = []
    for num in lsts2:
        rand_nums = [random.randint(1, K) for _ in range(num)]
        result.append(rand_nums)
    # print(result) 

    # 第4步:将可能不重复部分列表与重复列表合并, 得到每个编辑处理的新闻id列表模拟数据
    merged_result = []
    for sublist in result:
        # 注意:可能不重复部分列表 
        merged_list = list(set(sublist + lists))
        random.shuffle(merged_list) # 防止自动排序, 打乱处理
        merged_result.append(merged_list)
    return merged_result # 输出10个编辑分别处理的新闻id


if __name__ == "__main__":
    # 构造数据
    m, N, K = 8, 10, 60 # m为编辑们共同处理的新闻个数
    merged_result = generate_random_lists(m, N, K) # 生成编辑们各自处理的新闻id列表
    print('输入: ', merged_result)
    print("实际输出: ",find_common_news(N, K, merged_result))

输出:

期望输出:  [3, 16, 17, 22, 31, 32, 34, 52]
输入:  [[3, 40, 34, 22, 52, 14, 35, 31, 27, 32, 16, 17], [32, 8, 9, 3, 52, 36, 33, 44, 60, 12, 19, 17, 34, 43, 2, 10, 50, 45, 14, 42, 22, 41, 51, 55, 27, 11, 16, 39, 35, 15, 59, 49, 47, 28, 1, 26, 4, 31], [17, 33, 12, 24, 52, 47, 32, 23, 58, 27, 1, 16, 31, 18, 42, 60, 28, 19, 15, 3, 20, 53, 49, 57, 25, 21, 26, 9, 56, 35, 14, 4, 22, 5, 10, 13, 34, 8, 41], [40, 51, 21, 36, 34, 10, 52, 31, 57, 26, 41, 3, 32, 12, 9, 56, 39, 7, 59, 13, 17, 53, 22, 4, 27, 42, 16, 25], [35, 31, 27, 22, 39, 40, 11, 58, 30, 16, 56, 47, 17, 26, 34, 12, 53, 5, 3, 45, 1, 8, 32, 18, 52, 6], [9, 40, 26, 36, 39, 35, 54, 34, 17, 46, 43, 13, 52, 56, 37, 14, 45, 22, 6, 41, 25, 49, 20, 5, 7, 3, 31, 44, 50, 4, 30, 32, 16, 1], [2, 33, 32, 3, 8, 43, 31, 58, 42, 17, 1, 16, 52, 30, 59, 6, 34, 13, 29, 46, 51, 12, 22], [57, 31, 16, 14, 32, 9, 20, 18, 24, 30, 4, 17, 22, 27, 43, 12, 37, 2, 13, 59, 34, 53, 3, 48, 21, 55, 52, 25], [24, 3, 34, 31, 56, 19, 12, 8, 16, 52, 51, 10, 22, 32, 49, 33, 17, 2, 48, 15, 45, 42, 25, 60, 30, 46, 47, 36, 39, 58, 6, 20, 5, 37, 14], [17, 22, 58, 32, 52, 13, 5, 26, 34, 48, 3, 31, 27, 24, 2, 16]]
实际输出:  [3, 16, 17, 22, 31, 32, 34, 52]

二、函数关键信息

函数名称:find_common_news
参数N: 整数,表示编辑的数量。
参数K: 整数,表示新闻的总数。
news_ids: 一个包含N个列表的列表,每个列表包含一个编辑编辑过的新闻编号。
返回值:一个升序排列的列表,包含所有编辑共同编辑过的新闻编号。

三、程序设计原理

1、初始化一个空集合common_news_set,用于存储所有编辑共同编辑过的新闻编号。
2、将第一个编辑编辑过的新闻编号集合作为初始集合,存储到common_news_set中。
3、遍历第2到第N个编辑的新闻编号集合:
3.1、使用集合的intersection_update方法,将当前编辑的新闻编号集合与common_news_set取交集,并更新common_news_set。
3.2、这样,common_news_set中将保留与当前编辑共同编辑过的新闻编号,即找到所有编辑共同编辑过的新闻编号的交集。
4、将common_news_set转换为列表,并使用Python的sorted函数对列表进行升序排序。
5、返回排序后的列表作为结果。

四、复杂度分析

1、时间复杂度分析
1.1、使用集合的交集操作找出被所有编辑共同编辑过的新闻:遍历每个新闻集合进行交集操作,时间复杂度为O(K),其中K为所有编辑操作的总数。
1.2、排序:对交集结果进行排序,时间复杂度为O(NlogN),其中N为符合条件的新闻数量。
1.3、综合来看,时间复杂度为O(K + NlogN)。
2、空间复杂度分析
common_news_set集合:存储被所有编辑共同编辑过的新闻,最坏情况下需要存储所有新闻,空间复杂度为O(N)。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/671852.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

测试基础09:缺陷(bug)生命周期和缺陷(bug)管理规范

课程大纲 1、缺陷(bug)生命周期 2、缺陷(bug)提交规范 2.1 宗旨 简洁、清晰、可视化,减少沟通成本。 2.2 bug格式和内容 ① 标题:一级功能-二级功能-三级功能_(一句话描述bug:&…

eNsp——两台电脑通过一根网线直连通信

一、拓扑结构 二、电脑配置 ip和子网掩码,配置两台电脑处于同一网段 三、测试 四、应用 传文件等操作,可以在一台电脑上配置FTP服务器

含情脉脉的进程

冯诺依曼体系结构 一个计算机在工作的时候是怎样的呢? 我们所认识的计算机都是由一个个的硬件组件组成: 输入设备:键盘、鼠标、摄像头、话筒、磁盘、网卡 中央处理器(CPU):运算器、控制器 输出设备&#x…

Java多线程(04)—— 保证线程安全的方法与线程安全的集合类

一、CAS 与原子类 1. CAS CAS(compare and swap),是一条 cpu 指令,其含义为:CAS(M, A, B); M 表示内存,A 和 B 分别表示一个寄存器;如果 M 的值和 A 的值相同,则把 M 和 B 的值交…

我成功创建了一个Electron应用程序

1.创建electron项目命令: yarn create quick-start/electron electron-memo 2选择:√ Select a framework: vue √ Add TypeScript? ... No √ Add Electron updater plugin? ... Yes √ Enable Electron download mirror proxy? ... Yes 3.命令&a…

渲染100为什么是高性价比网渲平台?渲染100邀请码1a12

市面上主流的网渲平台有很多,如渲染100、瑞云、炫云、渲云等,这些平台各有特色和优势,也都声称自己性价比高,以渲染100为例,我们来介绍下它的优势有哪些。 1、渲染100对新用户很友好,注册填邀请码1a12有3…

09.责任链模式

09. 责任链模式 什么是责任链设计模式? 责任链设计模式(Chain of Responsibility Pattern)是一种行为设计模式,它允许将请求沿着处理者对象组成的链进行传递,直到有一个处理者对象能够处理该请求为止。这种模式的目的…

go语言linux安装

下载:https://go.dev/dl/ 命令行使用 wget https://dl.google.com/go/go1.19.3.linux-amd64.tar.gz解压下载的压缩包,linux建议放在/opt目录下 我放在/home/ihan/go_sdk下 sudo tar -C /home/ihan/go_sdk -xzf go1.19.3.linux-amd64.tar.gz 这里的参数…

STM32作业实现(一)串口通信

目录 STM32作业设计 STM32作业实现(一)串口通信 STM32作业实现(二)串口控制led STM32作业实现(三)串口控制有源蜂鸣器 STM32作业实现(四)光敏传感器 STM32作业实现(五)温湿度传感器dht11 STM32作业实现(六)闪存保存数据 STM32作业实现(七)OLED显示数据 STM32作业实现(八)触摸按…

谷歌发布文生视频模型——Veo,可生成超过一分钟高质量1080p视频

前期我们介绍过OpenAI的文生视频大模型-Sora 模型,其模型一经发布,便得到了大家疯狂的追捧。而Google最近也发布了自己的文生视频大模型Veo,势必要与OpenAI进行一个正面交锋。 Veo 是Google迄今为止最强大的视频生成模型。它可以生成超过一分…

学习小心意——python创建类与对象

在python中,类表示具有相同属性和方法的对象的集合,一般而言都是先定义类再创建类的实例,然后再通过类的实例去访问类的属性和方法 定义类 类中可以定义为数据成员和成员函数。数据成员用于描述对象特征(相当于看人的面貌&#…

针对大模型的上下文注入攻击

大型语言模型(LLMs)的开发和部署取得了显著进展。例如ChatGPT和Llama-2这样的LLMs,利用庞大的数据集和Transformer架构,能够产生连贯性、上下文准确性甚至具有创造性的文本。LLMs最初和本质上是为静态场景设计的,即输入…

【文档智能】符合人类阅读顺序的文档模型-LayoutReader原理及权重开源

引言 阅读顺序检测旨在捕获人类读者能够自然理解的单词序列。现有的OCR引擎通常按照从上到下、从左到右的方式排列识别到的文本行,但这并不适用于某些文档类型,如多栏模板、表格等。LayoutReader模型使用seq2seq模型捕获文本和布局信息,用于…

libcef.dll丢失的解决方法-多种libcef.dll亲测有效解决方法分享

libcef.dll是Chromium Embedded Framework (CEF)的核心动态链接库,它为开发者提供了一个将Chromium浏览器嵌入到本地桌面应用程序中的解决方案。这个库使得开发者能够利用Chromium的强大功能,如HTML5、CSS3、JavaScript等,来创建跨平台的应用…

Llama(一):Mac M1芯片运行Llama3

目录 安装Ollama for Mac 下载Llama 3模型 运行Llama3 试用Llama3 在命令行中使用Llama3 背景 本地环境:Mac M1,16GB内存 安装Ollama for Mac 官方地址 https://ollama.com/download/Ollama-darwin.zip 链接: 百度网盘 提取码: 8wqx 下载Llama 3模型 oll…

jmeter性能优化之tomcat配置与基础调优

一、 修改tomcat初始和最大堆内存 进入到/usr/local/tomcat7-8083/bin目录下,编辑catalina.sh文件,,默认堆内存是600m,初始堆内存和最大堆内存保持一致, 可以更改到本机内存的70%,对于Linux系统&#xff0…

《平渊》· 柒 —— 大道至简?真传一句话,假传万卷书!

《平渊》 柒 "真传一句话, 假传万卷书" 对于 "大道至简",不少专家可能会说出一大堆乱七八糟的名词, 比如这样: 所谓 "大道" 即支撑天地运转的 "系统自动力",更具体地来说,即是天地人以…

前端Vue小兔鲜儿电商项目实战Day07

一、会员中心 - 整体功能梳理和路由配置 1. 整体功能梳理 ①个人中心 - 个人信息和猜你喜欢数据渲染②我的订单 - 各种状态下的订单列表展示 2. 路由配置&#xff08;包括三级路由配置&#xff09; ①准备个人中心模板组件 - src/views/Member/index.vue <script setup&g…

【Leetcode 705 】设计哈希集合——数组嵌套链表(限制哈希Key)

题目 不使用任何内建的哈希表库设计一个哈希集合&#xff08;HashSet&#xff09;。 实现 MyHashSet 类&#xff1a; void add(key) 向哈希集合中插入值 key 。bool contains(key) 返回哈希集合中是否存在这个值 key 。void remove(key) 将给定值 key 从哈希集合中删除。如果…

构建智慧银行保险系统的先进技术架构

随着科技的不断发展&#xff0c;智慧银行保险系统正日益受到关注。在这个数字化时代&#xff0c;构建一个先进的技术架构对于智慧银行保险系统至关重要。本文将探讨如何构建智慧银行保险系统的先进技术架构&#xff0c;以提升服务效率、降低风险并满足客户需求。 ### 1. 智慧银…