宁波市奉化区建设局网站,wordpress漂亮破解主题,设计培训网页,特殊符号网站每日一句#xff1a;你的日积月累终会成为别人的望尘莫及 目录
常数时间的操作
选择排列
冒泡排列
【异或运算】
面试题#xff1a;
1#xff09;在一个整形数组中#xff0c;已知只有一种数出现了奇数次#xff0c;其他的所有数都出现了偶数次#xff0c;怎么找到… 每日一句你的日积月累终会成为别人的望尘莫及 目录
常数时间的操作
选择排列
冒泡排列
【异或运算】
面试题
1在一个整形数组中已知只有一种数出现了奇数次其他的所有数都出现了偶数次怎么找到出现了奇数次的数要求时间复杂度O(N),空间复杂度O1
2在一个整形数组中已知有两种数出现了奇数次其他的所有数都出现了偶数次怎么找到这两种数要求时间复杂度O(N),空间复杂度O1
插入排序
二分法的详解与扩展
1在一个有序数组中找某个数是否存在
2在一个有序数组中找大于等于某个数最左侧的位置
局部最小值问题
在一个数组中arr无序且任何两个相邻的数不相等求局部最小
对数器的概念和使用
递归行为和递归行为时间复杂度的估算
归并排序
小和问题
在一个数组中每一个数左边比当前数小的数累加起来叫做这个数组的小和。求一个数组的小和。
例[1,2,4,3,5]1左边比1小的数没有2左边比2小的数14左边比4小的数1,23左边比3小的数1,25左边比5小的数1,2,4,3
所以小和为11212124317
荷兰国旗问题
问题一
给定一个数组arr,和一个数num请把小于等于num的数放在数组的左边大于num的数放在数组的右边.要求额外空间复杂度O1时间复杂度ON
问题二
给定一个数组arr和一个数num请把小于num的数放在数组的左边等于num的数放在数组的中间大于num的数放在数组的右边.要求额外空间复杂度O1时间复杂度ON.
不改进的快速排序
堆
heapinsert过程
heapify过程
堆排序
已知一个几乎有序的数组几乎有序是指[如果把数组排好顺序的话每个元素移动的距离可以不超过K并且k相对于数组来说比较小]请选择一个合适的排序算法针对这个数据进行排序。
比较器的使用
桶排序思想下的排序
排序算法的稳定性及其汇总 常数时间的操作
一个操作如果和样本的数据量没有关系每次都是固定时间内完成的操作叫做常数操作
时间复杂度为一个算法流程中常数操作数量的一个指标。
常用O(读作bigO)来表示。具体来说先要对一个算法流程非常熟悉然后去写出这个算法流程中发生了多少常数操作进而总结出常数操作数量的表达式。
在表达式中只要高阶项不要低阶项的系数剩下的部分如果为f(N),那么时间复杂度为Of(N)
评价一个算法流程的好坏先看时间复杂度的指标然后再分析不同数据样本下的实际运行时间也就是“常数项时间”
数组、、-、*、/、位运算是常数操作
链表不是常数操作 额外空间复杂度
指这个流程需要多少额外空间才能支持计算下来
———————————————————————————————————————
选择排列
冒泡排列
相邻比较谁大谁往右移 【异或运算】
10^NN N^N0
2) 满足交换、结合律 a^bb^a (a^b)^ca^(b^c)
抖机灵法不用额外分配一块内存空间
int a甲 int b乙
aa^b; ——a甲^乙 b乙
ba^b; ——a甲^乙 b甲^乙^乙甲^0甲
aa^b; ——a甲^乙^甲乙^0乙 b甲
前提a和b在内存里是两块独立的区域i位置不能等于j位置否则会异或成0
面试题
1在一个整形数组中已知只有一种数出现了奇数次其他的所有数都出现了偶数次怎么找到出现了奇数次的数要求时间复杂度O(N),空间复杂度O1 ———————————————————————————————————————
2在一个整形数组中已知有两种数出现了奇数次其他的所有数都出现了偶数次怎么找到这两种数要求时间复杂度O(N),空间复杂度O1 先让eor从头异或到尾结尾时eora^b≠0a和b一定有一位不一样的假设第8位因为把整个数组分成2类第1类第8位是0第2类第8位是1 eor1只异或第8位是1的数eor1为a或b 3.eor^eor1为另一个a或b 把一个不为0的数最右侧的1提取出来的操作int rightoneeor(~eor1); 插入排序 时间复杂度O(),额外空间复杂度O(1) 算法流程按照最差情况来估计时间复杂度 数据状况不同会导致算法流程的时间复杂度不一样 选择排序和冒泡排序算法和数据状况无关 二分法的详解与扩展 1在一个有序数组中找某个数是否存在 2在一个有序数组中找大于等于某个数最左侧的位置 局部最小值问题 在一个数组中arr无序且任何两个相邻的数不相等求局部最小 优化方向1数据状况2问题标准 对数器的概念和使用 有一个你想要测的方法a实现复杂度不好但是容易实现的方法b实现一个随机样本产生器把方法a和方法b跑相同的随机样本看得到的结果是否一样如果有一个随机样本使得比对结果不一致打印样本进行人工干预改对方法a或者方法b当样本数量很多时对比测试依然正确可以确定方法a已经正确 递归行为和递归行为时间复杂度的估算 用递归方法找一个数组中的最大值系统上到底怎么做的 Master公式的使用 T(N)a*T(Nb)O() d 复杂度为O()d 复杂度为O()d 复杂度为O() 中点midLL(R-L)1 归并排序 整体就是一个简单递归左边排好序右边排好序让其整体有序让其整体有序的过程用了外排序方法利用master公式来求解时间复杂度归并排序的实质 时间复杂度O,额外空间复杂度ON 选择、冒泡、插入O浪费了大量的比较行为 归并排序比较行为没有被浪费 比较行为被留下来了变成了一个整体有序的部分信息往下传递 ————————————————————————————————————— 归并排序的扩展 小和问题 在一个数组中每一个数左边比当前数小的数累加起来叫做这个数组的小和。求一个数组的小和。 例[1,2,4,3,5]1左边比1小的数没有2左边比2小的数14左边比4小的数1,23左边比3小的数1,25左边比5小的数1,2,4,3 所以小和为11212124317 逆序对问题 在一个数组中左边的数如果比右边的数大则这两个数构成一个逆序对请打印所有逆序对。 例如数组[3,2,4,5,0],存在逆序对[3,2]、[3,0]、[2,0]、[4,0]、[5,0] ————————————————————————————————————— 荷兰国旗问题 问题一 给定一个数组arr,和一个数num请把小于等于num的数放在数组的左边大于num的数放在数组的右边.要求额外空间复杂度O1时间复杂度ON 问题二 给定一个数组arr和一个数num请把小于num的数放在数组的左边等于num的数放在数组的中间大于num的数放在数组的右边.要求额外空间复杂度O1时间复杂度ON. ————————————————————————————————————— 不改进的快速排序 1把数组范围中的最后一个数作为划分值然后把数组通过荷兰国旗问题分成三个部分 左侧划分值、中间划分值、右侧划分值 2对左侧范围和右侧范围递归执行 分析 划分值越靠近两侧复杂度越高划分值越靠近中间复杂度越低可以轻而易举的举出最差的例子所以不改进的快速排序时间复杂度为O 快排额外空间复杂度O 堆 堆结构就是用数组实现的完全二叉树结构完全二叉树中如果每棵子树的最大值都在顶部就是大根堆完全二叉树中如果每棵子树的最小值都在顶部就是小根堆堆结构的heapInsert一路往上走与heapify一路往下走操作堆结构的增大和减少优先级队列结构就是堆结构 heapinsert过程 heapify过程 堆排序 1.先让整个数组都变成大根堆结构建立堆的过程 )从上到下的方法时间复杂度ON从下到上的方法时间复杂度O(N) 2把堆的最大值和堆末尾的值交换然后减少堆的大小之后再去调整堆一直周而复始时间复杂度ON 3. 堆的大小减小成0之后排序完成 堆排序扩展题目 已知一个几乎有序的数组几乎有序是指[如果把数组排好顺序的话每个元素移动的距离可以不超过K并且k相对于数组来说比较小]请选择一个合适的排序算法针对这个数据进行排序。 小根堆在Java中优先级队列意思 PriorityQueueInteger heapnew PriorityQueue(); 1.扩容怎么办 扩容次数O水平 每次扩容ON水平 整体O水平 单位平均下来O水平 2.系统写好的堆不支持已经实现了的堆用很轻的代价使某一结构变值调整自己写的堆 比较器的使用 比较器的实质就是重载比较运算符比较器可以很好的应用在特殊标准的排序上比较器可以很好的应用在根据特殊标准排序的结构上 ——————————————————————————————————————— 不基于比较的排序都是根据数据状况做的排序 桶排序思想下的排序 计数排序基数排序 分析 桶排序思想下的排序都是不基于比较的排序时间复杂度ON额外空间复杂度ON应用范围有限需要样本的数据状况满足桶的划分 排序算法的稳定性及其汇总 同样值的个体之间如果不因为排序而改变相对次序就是这个排序是有稳定性的否则就没有 不具有稳定性的排序选择排序、快速排序、堆排序 具备稳定性的排序冒泡排序、插入排序、归并排序、一切桶排序思想下的排序 [相等的时候不让交换保持了稳定性] 目前没有找到时间复杂度O,额外空间复杂度O1又稳定的排序 选择排序 从0~N-1位置上选一最小值放0位置上…… 冒泡排序 0~1上比较交换1~2,2~3,3~4,4~5,5位置排好 0~1上比较交换1~2,2~3,3~4 ,4位置排好 …… 插入排序 0~0有序 0~1交换、有序 0~2交换、有序 时间复杂度 额外空间复杂度 稳定性 选择 O O1 × 冒泡 O O1 √ 插入 O O1 √ 归并 O ON √ 快排 O O × 堆 O O1 × 常见的坑 归并排序的额外空间复杂度可以变为O1但非常难不需要掌握有兴趣可以搜“归并排序内部缓存法”“原地归并排序”的帖子都是垃圾会让归并排序的时间复杂度变成O快排可以做到稳定性但非常难不需要掌握可以搜“01 stable sort”所有的改进都不重要因为目前没有找到时间复杂度O额外空间复杂度O1又稳定的排序有一道题目是奇数放在数组左边偶数放在数组右边还要求原始的相对次序不变碰到这个问题可以怼面试官 工程上对排序的改进 充分利用O和O排序各自的优势稳定性的考虑 大样本量时 调度 快排 O 小样本量时 插入 O
