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

排序

一、数据流中的中位数

题目描述:如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。

解题思路:这里考虑到是从数据流中获取,那么数据就是不断更新的。使用大顶堆来存放排序后前半部分(小的数),使用小顶堆来存放排序后的后半部分(大的数)。其中需要注意的是以下堆的几个操作:

  1. 将元素入堆:m.push_back(x);

  1. 向堆中添加新的元素作为叶子节点:push_heap(m.begin(),m.end(),less<int>())

  1. 堆顶元素出堆:

  1. pop_heap(m.begin(),m.end(),less<int>())

  1. m.pop_back()

classSolution {
private:vector<int>max;vector<int>min;
public:voidInsert(int num){int size=max.size()+min.size(); //统计整个数据的长度if((size&1)==0) //这里先判断奇偶性,如果是奇数个数字,则遍历大顶堆,统计前半部分数组。{if(max.size()>0&&num<max[0]){max.push_back(num);push_heap(max.begin(),max.end(),less<int>()); //添加数据流中的新元素,作新的叶节点num=max[0]; //获取堆顶元素以便放到后半部分数据组成的小顶堆中pop_heap(max.begin(),max.end(),less<int>()); //堆顶元素出堆max.pop_back();}//将大顶堆中的堆顶元素放到小顶堆中以便平衡元素min.push_back(num);push_heap(min.begin(),min.end(),greater<int>());}else{if(min.size()>0&&num>min[0]){min.push_back(num);push_heap(min.begin(),min.end(),greater<int>()); //添加数据流中的新元素num=min[0]; //获取堆顶元素以便放到前半部分数据组成的大顶堆中pop_heap(min.begin(), min.end(),greater<int>()); //堆顶元素出堆min.pop_back();}//将小顶堆中的堆顶元素放到大顶堆中以便平衡元素max.push_back(num);push_heap(max.begin(), max.end(),less<int>()); //堆顶元素出堆}}doubleGetMedian(){int size=max.size()+min.size();if(size<=0) return0;if((size&1)==0) //判断奇偶性return (max[0]+min[0])/2.0;elsereturn min[0];}};

二、最小的K个数

题目描述:输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。

解题思路

  • 方法一:使用sort排一遍序,如果没有时间复杂度的要求的话,可以OK没问题。

classSolution {
public:vector<int> GetLeastNumbers_Solution(vector<int> input, int k){vector<int> v;if(k>input.size())return v;sort(input.begin(),input.end());for(int i=0;i<k;i++)v.push_back(input[i]);return v;      }
};

  • 方法二:使用快排的思想,通过函数计算,使k以前的数都小于k,k之后的数都大于k,这样,最终只需要取前k个数即可。时间复杂度o(n)。

#include<iostream>#include<vector>usingnamespace std;
inteach_sort(vector<int>&a,int i,int j){int tmp=a[i];if(i<j){while(i<j&&a[j]>tmp) j--;if(i<j) a[i]=a[j];while(i<j&&a[i]<tmp) i++;if(i<j) a[j]=a[i];}a[i]=tmp;return i;
}
voidkp_sort(vector<int>&Array,int Begin,int End){if(Begin<End){int tmp=each_sort(Array,Begin,End); //查找每次分配完成的中点kp_sort(Array,Begin,tmp-1); //左边kp_sort(Array,tmp+1,End); //右边}
}
intmain(){vector<int>arr{1,3,2,4,6,5,7,9,13,12};int k;cin>>k;kp_sort(arr,0,arr.size()-1);for(int j=0;j<k;j++)cout<<arr[j]<<',';return0;
}

快排java实现:

classSolution {publicint[] getLeastNumbers(int[] arr, int k) {randomizedSelected(arr, 0, arr.length - 1, k);int[] vec = newint[k];for (inti=0; i < k; ++i) {vec[i] = arr[i];}return vec;}privatevoidrandomizedSelected(int[] arr, int l, int r, int k) {if (l >= r) {return;}intpos= randomizedPartition(arr, l, r);intnum= pos - l + 1;if (k == num) {return;} elseif (k < num) {randomizedSelected(arr, l, pos - 1, k);} else {randomizedSelected(arr, pos + 1, r, k - num);}}// 基于随机的划分privateintrandomizedPartition(int[] nums, int l, int r) {inti=newRandom().nextInt(r - l + 1) + l;swap(nums, r, i);return partition(nums, l, r);}privateintpartition(int[] nums, int l, int r) {intpivot= nums[r];inti= l - 1;for (intj= l; j <= r - 1; ++j) {if (nums[j] <= pivot) {i = i + 1;swap(nums, i, j);}}swap(nums, i + 1, r);return i + 1;}privatevoidswap(int[] nums, int i, int j) {inttemp= nums[i];nums[i] = nums[j];nums[j] = temp;}
}

三、剑指 Offer II 032. 有效的变位词

思路:排序

classSolution {publicbooleanisAnagram(String s, String t) {if(s.length()!=t.length()||s.equals(t)){returnfalse;}char[] a=s.toCharArray();char[] b=t.toCharArray();Arrays.sort(a);Arrays.sort(b);return Arrays.equals(a,b);}
}

相关文章:

排序

一、数据流中的中位数题目描述&#xff1a;如何得到一个数据流中的中位数&#xff1f;如果从数据流中读出奇数个数值&#xff0c;那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值&#xff0c;那么中位数就是所有数值排序之后中间两个数的平均值。…...

Android DataStore Proto存储接入流程详解与使用

一、介绍 通过前面的文字&#xff0c;我们已掌握了DataStore 的存储&#xff0c;但是留下一个尾巴&#xff0c;那就是Proto的接入。 Proto是什么&#xff1f; Protobuf&#xff0c;类似于json和xml&#xff0c;是一种序列化结构数据机制&#xff0c;可以用于数据通讯等场景&a…...

HiEV洞察 | 卖一台亏半台,激光雷达第一股禾赛隐忧仍在

作者 | 感知君Alex 编辑 | 王博2月9日晚&#xff0c;禾赛在万众瞩目下登陆纳斯达克&#xff0c;发行价19美元每股&#xff0c;首日涨超11%&#xff0c;市值超过Luminar&#xff0c;登顶全球市值最高的激光雷达公司。 随后两个交易日&#xff0c;其股价均有不同程度的涨幅&#…...

面试题61. 扑克牌中的顺子

题目 从若干副扑克牌中随机抽 5 张牌&#xff0c;判断是不是一个顺子&#xff0c;即这5张牌是不是连续的。2&#xff5e;10为数字本身&#xff0c;A为1&#xff0c;J为11&#xff0c;Q为12&#xff0c;K为13&#xff0c;而大、小王为 0 &#xff0c;可以看成任意数字。A 不能视…...

有特别有创意的网站设计案例

有人说 UI 设计师集艺术性与科学性于一身&#xff0c;不仅需要对工具的使用熟练&#xff0c;更需要对美术艺术有一定的基础了解。如果想要成为优秀的 UI 设计师是一个需要磨砺的过程&#xff0c;需要不断的学习和积累&#xff0c;多看多练多感受&#xff0c;其中对于优质的设计…...

Python基础-数据类型之列表

一、列表的定义 name ["小明", "小红", "笑笑"] 二、列表的使用 除了序列中的操作&#xff0c;列表还有一些其他的操作。 &#xff08;1&#xff09;不使用列表方法对列表进行修改 1&#xff1a;通过索引修改列表中的值 name ["Kit…...

Linux系统基本设置:网络设置(三种界面网络地址配置)

网络地址配置&#xff1a;图形界面配置、命令行界面配置、文本图形界面配置 命令行界面配置 查看网络命令&#xff1a; 想要知道你有多少网卡&#xff0c;都可以通过这两个命令来查看 手动设置网络参数&#xff0c;我们可以使用nmcli这个命令来设置&#xff0c;我们需要知道…...

MySQL(二):查询性能分析

文章目录一、使用explain进行分析二、如何优化数据的访问三、如何重构大查询一、使用explain进行分析 Explain 用来分析 SELECT 查询语句&#xff0c;开发人员可以通过分析 Explain 结果来优化查询语句。 比较重要的字段有&#xff1a; select_type : 查询类型&#xff0c;有…...

Java基础-类加载器

写在前面的话&#xff1a; 基础加强包含了&#xff1a; 反射&#xff0c;动态代理&#xff0c;类加载器&#xff0c;xml&#xff0c;注解&#xff0c;日志&#xff0c;单元测试等知识点 其中最难的是反射和动态代理&#xff0c;其他知识点都非常简单 由于B站P数限制&#xff0c…...

Python 使用pandas处理Excel —— 快递订单处理 数据匹配 邮费计算

问题背景 有表A&#xff0c;其数据如下 关键信息是邮寄地址和单号。 表B&#xff1a; 关键信息是运单号和重量 我们需要做的是&#xff0c;对于表A中的每一条数据&#xff0c;根据其单号&#xff0c;在表B中查找到对应的重量。 在表A中新增一列重量&#xff0c;将刚才查到的…...

【黑马SpringCloud(7)】分布式事务

分布式事务事务的ACID原则分布式事务理论基础CAP定理BASE理论Seataseata的部署seata的集成事务模式XA模式Seata的XA模型优缺点实现XA模式AT模式案例&#xff1a;AT模式更新数据脏写问题优缺点实现AT模式TCC模式流程分析Seata的TCC模型事务悬挂和空回滚实现TCC模式优缺点SAGA模式…...

百度地图API添加自定义标记解决单html文件跨域

百度地图API添加自定义标记解决单html文件跨域 因为要往百度地图上添加一些标注点&#xff0c;而且这些标注点要用自定义的图片&#xff0c;而且只能使用单html文件&#xff0c;不能使用服务器&#xff08;也别问为什么&#xff0c;就是这么个需求&#xff09;&#xff0c;做起…...

如何停止/重启/启动Redis服务

一、命令行直接启动/停止/重启redis 可以直接通过下面的命令启动/停止/重启redis /etc/init.d/redis-server start 启动redis服务 /etc/init.d/redis-server stop 停止redis服务 /etc/init.d/redis-server restart 重启redis服务1、启动redis服务…...

python 的selenium自动操控浏览器教程(2)

人生苦短&#xff0c;我用py 文章目录人生苦短&#xff0c;我用py关于部分网页无法找到元素的问题1方案1方案2关于部分网页无法找到元素的问题2解决方案被网站检查出来我们使用了selenium了怎么办&#xff1f;如何实现前进后退当使用py删除文件时报禁止访问怎么办怎么使用py实现…...

【Deformable Convolution】可变形卷积记录

every blog every motto: You can do more than you think. https://blog.csdn.net/weixin_39190382?typeblog 0. 前言 可变形卷积记录 1. 正文 预印版&#xff1a; Deformable Convolutional Networks v1 Deformable ConvNets v2: More Deformable, Better Results 发表版…...

Oracle-Mysql 函数转换

Oracle-Mysql 函数转换limit <> ROWNUMcast <> TO_NUMBERcast as signedcast as unsignedregexp a_\\d <> REGEXP_LIKEschema() <> SELECT USER FROM DUALinformation_schema.COLUMNS表 <> ALL_TAB_COLUMNS表unix_timestampfrom_unixtime <&g…...

【Kafka】一.认识Kafka

kafka是一个分布式消息队列。由 Scala 开发的高性能跨语言分布式消息队列&#xff0c;单机吞吐量可以到达 10w 级&#xff0c;消息延迟在 ms 级。具有高性能、持久化、多副本备份、横向扩展能力。 生产者往队列里写消息&#xff0c;消费者从队列里取消息进行业务逻辑。 一般在…...

Linux软件管理YUM

目录 yum配置文件 创建仓库 yum查询功能 yum安装与升级功能 yum删除功能 yum仓库产生的问题和解决之道 yum与dnf 网络源 YUM就是通过分析RPM的标头数据后&#xff0c;根据各软件的相关性制作出属性依赖时的解决方案&#xff0c;然后可以自动处理软件的依赖属性问题&…...

【自学MYSQL】MySQL Windows安装

MySQL Windows安装 MySQL Windows下载 首先&#xff0c;我们打开 MySQL 的官网&#xff0c;网址如下&#xff1a; https://dev.mysql.com/downloads/mysql/在官网的主页&#xff0c;我们首先根据我们的操作系统&#xff0c;选择对应的系统&#xff0c;这里我们选择 Windows&…...

Linux c编程之常用技巧

一、说明 在Linux C的实际编程应用中,有很多有用的实践技巧,编程中掌握这些知识,会对编程有事半功倍的效果。 二、常用技巧 2.1 if 变量条件的写法 main.c: #include <stdio.h>int main(int argc, char *argv[]) {int a =...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...