当前位置: 首页 > 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 =...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

验证redis数据结构

一、功能验证 1.验证redis的数据结构&#xff08;如字符串、列表、哈希、集合、有序集合等&#xff09;是否按照预期工作。 2、常见的数据结构验证方法&#xff1a; ①字符串&#xff08;string&#xff09; 测试基本操作 set、get、incr、decr 验证字符串的长度和内容是否正…...

__VUE_PROD_HYDRATION_MISMATCH_DETAILS__ is not explicitly defined.

这个警告表明您在使用Vue的esm-bundler构建版本时&#xff0c;未明确定义编译时特性标志。以下是详细解释和解决方案&#xff1a; ‌问题原因‌&#xff1a; 该标志是Vue 3.4引入的编译时特性标志&#xff0c;用于控制生产环境下SSR水合不匹配错误的详细报告1使用esm-bundler…...

IP选择注意事项

IP选择注意事项 MTP、FTP、EFUSE、EMEMORY选择时&#xff0c;需要考虑以下参数&#xff0c;然后确定后选择IP。 容量工作电压范围温度范围擦除、烧写速度/耗时读取所有bit的时间待机功耗擦写、烧写功耗面积所需要的mask layer...

学习 Hooks【Plan - June - Week 2】

一、React API React 提供了丰富的核心 API&#xff0c;用于创建组件、管理状态、处理副作用、优化性能等。本文档总结 React 常用的 API 方法和组件。 1. React 核心 API React.createElement(type, props, …children) 用于创建 React 元素&#xff0c;JSX 会被编译成该函数…...