当前位置: 首页 > news >正文

基于Python3的数据结构与算法 - 10 计数排序

一、问题

对列表进行排序,已知列表中的数范围都在0到100之间。设计时间复杂度为O(n)的算法。

二、解决思路

我们已知数字的范围,那么我们可以将数字的个数得到:

例如:有一个0~5的列表

[1,3,2,4,1,2,3,1,3,5]   则共有0个0,3个1,2个2,3个3,1个4,1个5。

再直接进行排序即可,可以将原来的列表覆盖。

示例代码如下:

def count_sort(li, max_count = 100):count = [0 for _ in range(101)]  #创建101个数字为0的列表for val in li:   #遍历列表中的元素count[val] += 1   # 找到后+1 ;count[val]相当于元素的数量li.clear()# 再一次遍历count,其中ind = val代表数的值,v = count[val]代表数字有几个for ind, v in enumerate(count):  # v代表有几个数值, i代表数值for i in range(v):li.append(ind)import random
li = [random.randint(0,100) for i in range(100)]
print(li)
count_sort(li)
print(li)

输出结果如下:

注意点:

  1. 此时n为li的长度,代码中虽然是一共有两层循环,但是长度都不是n,两层循环的复杂度一共为O(n) 。
  2. 计数排序使用需要一个已知条件:已知数值的范围。

相关文章:

基于Python3的数据结构与算法 - 10 计数排序

一、问题 对列表进行排序,已知列表中的数范围都在0到100之间。设计时间复杂度为O(n)的算法。 二、解决思路 我们已知数字的范围,那么我们可以将数字的个数得到: 例如:有一个0~5的列表 [1,3,2,4,1,2,3,1,3,5] 则共有0个0&am…...

力扣206反转链表

206.反转链表 力扣题目链接(opens new window) 题意:反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 1,双指针 2,递归。递归参考双指针更容易写, 为什么不用头插…...

【python实战】--图片创作视频

系列文章目录 文章目录 系列文章目录前言一、VideoWriter_fourcc()常见的编码参数二、使用步骤1.引入库 总结 前言 一、VideoWriter_fourcc()常见的编码参数 cv2.VideoWriter_fourcc(‘M’, ‘P’, ‘4’, ‘V’)MPEG-4编码 .mp4 可指定结果视频的大小cv2.VideoWriter_fourcc…...

数据挖掘实战 —— 抖音用户浏览行为数据分析与挖掘(代码部分)

文章: 数据挖掘实战 —— 抖音用户浏览行为数据分析与挖掘(一) 数据挖掘实战 —— 抖音用户浏览行为数据分析与挖掘(二) 数据挖掘实战 —— 抖音用户浏览行为数据分析与挖掘(总) 代码: 数据挖掘实战 —— 抖音用户浏览行为数据分析与挖掘(代码…...

AWS EKS(AWS云里面的K8S)

问题 初步使用EKS 步骤 安装AWS CLI 第一步是在自己的笔记本电脑上面安装AWS提供的CLI(命令行工具),这里就不详细介绍了,都是next的步骤。具体可以参考啊aws cli安装的相关教程网页,具体地址如下: http…...

Azkaban 大数据 任务调度

参考视频:尚硅谷大数据Azkaban 3.x教程(全新发布)_哔哩哔哩_bilibili Azkaban: 是一个定时、批量工作流任务调度器(工作流程调度,定时调度) 常见的开源调度系统: 简单单一的任务调度: Linux的…...

从预训练到通用智能(AGI)的观察和思考

1.预训练词向量 预训练词向量(Pre-trained Word Embeddings)是指通过无监督学习方法预先训练好的词与向量之间的映射关系。这些向量通常具有高维稠密特征,能够捕捉词语间的语义和语法相似性。最著名的预训练词向量包括Google的Word2Vec&#…...

四种垃圾回收算法

1.标记清除算法 该算法先标记,后清除,将所有需要回收的算法进行标记,然后清除;这种算法的缺点是:效率比较低;标记清除后会出现大量不连续的内存碎片,这些碎片太多可能会使存储大对象会触发GC回…...

stm32f103zet6笔记1-led工程

1、选择串口调试 2、LED0连接到PB5,PB5设置为推挽输出。PE5同理。 3、生成成对的.c,.h文件。 4、debugger选择j-link。 5、connection选择SWD。 6、编写bsp_led.c,bsp_led.h文件。 7、下载调试,可以看到LED0 500ms闪烁一次,LED1 1000ms闪烁一…...

OpenDDS的Qos策略

目录 1、前言2、QoS策略2.1、LIVELINESS2.2、RELIABILITY2.3、HISTORY2.4、DURABILITY2.5、DURABILITY_SERVICE2.6 、RESOURCE_LIMITS2.7、PARTITION2.8、DEADLINE2.9、LIFESPAN2.10、USER_DATA2.11、TOPIC_DATA2.12、GROUP_DATA2.13、TRANSPORT_PRIORITY2.14、LATENCY_BUDGET2…...

string基本操作(C++)

增 1.1 “” str str ss;cout << str << endl; //234561提取字串 2.1 substr substr(pos): 提取从位置pos开始到末尾的子串。 #include <iostream> #include <string> using namespace std;int main(){string str "123456";//substr(pos…...

【网站项目】123网上书城系统

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…...

LeetCode148.排序链表

题目 给你链表的头结点 head &#xff0c;请将其按 升序 排列并返回 排序后的链表 。 示例 输入&#xff1a;head [4,2,1,3] 输出&#xff1a;[1,2,3,4] 输入&#xff1a;head [-1,5,3,4,0] 输出&#xff1a;[-1,0,3,4,5] 输入&#xff1a;head [] 输出&#xff1a;[] 思路…...

qt学习:网络调试助手客户端+服务端

目录 客户端 步骤 ui界面配置​编辑 添加头函数&#xff0c;类成员数据&#xff0c;类成员函数 添加模块 构造函数 连接按钮 收到来自服务器的数据触发 发送按钮 断开按钮 向textEditRev文本编辑器中插入指定颜色的文本 服务端 步骤 ui界面配置 添加头函数&…...

C语言拾遗

函数的地址传递&#xff1a; 函数体内部想要修改函数体外部变量值的时候&#xff0c;使用地址传递 int set(int *pa) {//功能 } int main(void) {int a0;set(&a);//此时a的值经过set函数的修改&#xff0c;且传递到了main函数 } 函数体内想修改函数体外部指针的值的时候…...

大唐杯学习笔记:Day4

1.1NR帧结构 5G NR中,依然采用一帧10ms,并将一帧分为10子帧,每个子帧为1ms。每个子帧包含几个时隙(slot),每个时隙由14个OFDM符号构成(在常规CP下)。 μ \mu μ Δ f 2 μ ∗ 15 [ K H Z ] \Delta f2^{\mu}*15[KHZ] Δf2μ∗15[KHZ]Cyclic prefix015Normal130Normal260Normal…...

docker基线安全修复和容器逃逸修复

一、docker安全基线存在的问题和修复建议 1、将容器的根文件系统挂载为只读 修复建议&#xff1a; 添加“ --read-only”标志&#xff0c;以允许将容器的根文件系统挂载为只读。 可以将其与卷结合使用&#xff0c;以强制容器的过程仅写入要保留的位置。 可以使用命令&#x…...

ZooKeeper概述

ZooKeeper是一个开源的分布式协调服务&#xff0c;由Apache Software Foundation维护。它主要用于解决分布式应用中遇到的一些最常见问题&#xff0c;如命名服务、状态同步、配置管理和群集管理等。通过提供一套简单但强大的API&#xff0c;ZooKeeper使得从简单的锁服务到复杂的…...

【sgCollapseBtn】自定义组件:底部折叠/展开按钮

特性&#xff1a; 支持自定义折叠状态支持自定义标签名称 sgCollapseBtn源码 <template><div :class"$options.name" click"show !show" :placement"placement"><div class"collapse-btns"><div class"c…...

如何根据玩家数量和游戏需求选择最合适的服务器配置?

根据玩家数量和游戏需求选择最合适的服务器配置&#xff0c;首先需要考虑游戏的类型、玩家数量、预计的在线时间以及对内存和CPU性能的需求综合考虑。对于大型多人在线游戏&#xff0c;如MMORPG或MOBA等&#xff0c;由于需要更多的CPU核心数来支持更复杂的游戏逻辑和处理大量数…...

SEO 搜索引擎公司如何提高网站的流量

SEO 搜索引擎公司如何提高网站的流量 在当今互联网时代&#xff0c;网站的流量直接影响着企业的品牌知名度和市场竞争力。对于许多企业来说&#xff0c;SEO&#xff08;搜索引擎优化&#xff09;成为了提升网站流量的关键途径。SEO 搜索引擎公司究竟如何有效提高网站的流量呢&…...

从手机芯片到AI芯片:NoC拓扑结构怎么选?(Mesh、Torus、树形对比指南)

从手机芯片到AI芯片&#xff1a;NoC拓扑结构选型实战指南 当你在设计一款边缘AI芯片时&#xff0c;面对数十个需要高效协同的计算单元&#xff0c;最令人头疼的问题之一就是&#xff1a;如何选择片上网络(NoC)的拓扑结构&#xff1f;这个问题看似简单&#xff0c;实则牵一发而动…...

Go 网络编程超时控制方案

Go网络编程中的超时控制方案 在分布式系统和微服务架构盛行的今天&#xff0c;网络通信的稳定性成为关键。Go语言凭借其高效的并发模型和简洁的语法&#xff0c;成为网络编程的热门选择。网络环境复杂多变&#xff0c;超时控制是确保系统健壮性的重要手段。本文将介绍Go网络编…...

OpenClaw技能开发:让Kimi-VL-A3B-Thinking理解自定义图表类型

OpenClaw技能开发&#xff1a;让Kimi-VL-A3B-Thinking理解自定义图表类型 1. 为什么需要定制图表解析能力 上周我尝试用OpenClaw自动整理一批金融研报时&#xff0c;遇到了一个典型问题&#xff1a;当Kimi-VL-A3B-Thinking遇到K线图时&#xff0c;它会把蜡烛图简单描述为&quo…...

快照模式 vs 命令模式:一篇分清什么时候用谁

在做带撤销、回滚、历史记录的功能时&#xff0c;我们最常纠结两个设计模式&#xff1a;快照模式&#xff08;备忘录模式&#xff09;和命令模式。很多同学容易混淆&#xff0c;其实核心区别一句话就能记住&#xff1a; 快照存数据&#xff0c;命令存动作。 下面用最清晰、最好…...

嵌入式系统引导程序uboot原理与应用详解

1. 为什么嵌入式系统需要uboot1.1 计算机系统启动的基本原理任何计算机系统启动时都需要一个引导程序来完成硬件初始化和操作系统加载的工作。无论是PC机还是嵌入式设备&#xff0c;这个基本原理都是相通的。在PC架构中&#xff0c;这个引导程序叫做BIOS&#xff08;基本输入输…...

网络基础必问:简单谈谈你对DNS的理解?原理+流程图+通俗讲解

网络基础必问&#xff1a;简单谈谈你对DNS的理解&#xff1f;原理流程图通俗讲解一、前言二、DNS 是什么&#xff1f;&#xff08;一句话核心&#xff09;三、为什么需要 DNS&#xff1f;四、DNS 完整工作流程图&#xff08;最清晰&#xff09;五、DNS 解析步骤&#xff08;简单…...

OpenClaw飞书机器人配置:Phi-3-mini-128k-instruct对话式任务触发

OpenClaw飞书机器人配置&#xff1a;Phi-3-mini-128k-instruct对话式任务触发 1. 为什么选择飞书OpenClawPhi-3的组合&#xff1f; 去年团队规模扩张到15人时&#xff0c;我突然发现每天要花2小时处理各种琐碎请求&#xff1a;"下周会议材料准备好了吗&#xff1f;"…...

基于MATLAB与SVM实现河道水面漂浮物的自动检测与识别

摘要&#xff1a;河道水面漂浮物不仅影响水环境质量&#xff0c;还威胁水利设施安全和水生态健康。传统人工巡检方式效率低、成本高&#xff0c;难以满足大范围、实时化的 监测需求。针对上述问题&#xff0c;本文基于 MATLAB 平台&#xff0c;结合支持向量机&#xff08;SVM&a…...

Python @contextmanager 装饰器完全指南

在Python编程实践中&#xff0c;资源管理是一个永恒的话题。无论是文件句柄、数据库连接还是临时状态变更&#xff0c;我们都需要确保资源被正确分配并在使用后得到妥善清理。虽然传统的try...finally语句可以解决这个问题&#xff0c;但Python提供了更加优雅的解决方案——上下…...