kubeflow 以太坊 java设计模式 properties Markdown编辑器 方法 Jetson Nano Android开发 json enums process arm bootstrap后台模板 后台管理模板下载 ddos压力测试 郑州网络 access教学视频 sql视频教程 jquery移除子元素 android富文本框架 mser算法 python环境搭建 python变量类型 简单python脚本实例 java教程 java日期 javaif语句 java中泛型 java匿名对象 java中collection java查看变量类型 黑客攻防实战入门 莫愁脚本 球中的小鬼 abaqus最新版本 ipad锁屏 脚本错误怎么解决 算法笔记 如何用ai设计字体 fastcgi
当前位置: 首页 > 学习教程  > 编程语言

分块思想

2021/1/13 20:39:13 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

还是用问题引入&#xff1a; 给出一个非负整数序列A&#xff0c;元素个数为N&#xff08;N<105&#xff0c;A[i]<105&#xff09;&#xff0c;在有可能随时添加或删除元素的情况下&#xff0c; 实时查询序列中第K大的元素&#xff08;即把序列元素从小到大排序后从左到右…

还是用问题引入:

给出一个非负整数序列A,元素个数为N(N<=105,A[i]<=105),在有可能随时添加或删除元素的情况下, 实时查询序列中第K大的元素(即把序列元素从小到大排序后从左到右的第K个元素,比如{2, 7, 5, 1, 6}中第3大元素是5,但是插入元素4之后第3大的元素就是4了)

在查询过程中元素可能发生改变(插入、删除等),就称为在线查询,反之叫离线查询。上面的问题就是在线查询。
如果直接暴力做法来做,在每次添加或删除元素之后就要用O(n)的时间复杂度来移动序列元素,效率将及其低下。这种解决方法有很多,这里介绍最容易理解的一种——分块思想。
分块就是将有序元素分为若干块。比如可以把{1, 2, 4, 9, 12, 34, 56, 78, 87}分为3块{1, 2, 4}{9, 12, 34}{56, 78, 87}。一般为了高效率,对有N个元素的有序序列来说除了最后一块以外,每个块中元素的个数都是√(N)(取下界)个,块数就是√(N)(取上界)个。比如11个数,可以分为√(N)(取下界)即3个,一共分为√(N)(取上界)即4块,块内元素分别有3、3、3、2个。

现在利用分块法解决问题。题目中因为说明N<=105,所以这里设置一个hash数组table[100001],其中table[i]表示整数x的当前存在个数。然后将这100000个数进行逻辑上分块,一共分为√(100000)(取上界)即317块,每块有√(100000)(取下界)个即316个数。用一个统计数组block[317]记录每块的数据,block[i]表示第1块中存在的元素个数。
假设要新增一个元素x,可以通过x / 316计算出x所在的块,然后让block[x / 316] + 1表示该块中的元素再加上一个;同时令table[x]加1表示整数x的当前存在个数加1。比如新增334这个元素,先通过334 / 316算出334所在块号为1,然后令block[1]++,表示1号块增加了一个元素,再令table[334]++,表示334存在的个数多了1。要删除元素也是同理。
通过这方法,现在增加、删除元素的时间复杂度变成了O(1)。
然后开始找第K个元素,先将block数组累加得到前i-1个块中存在的元素总个数,然后加上i号块的元素个数判断总个数是否到达K,如果到达说明第K大的数就在当前的块中,此时只需再遍历该块即可。

【例】数据范围为0 ~ 8,则可以分为3块,0号块负责0 ~ 2,1号块负责3 ~ 5,2号块负责6 ~ 8.现在假设有0,1,3,4,4,5,8,此时block数组和table数组情况如下:
block[0] = 2,0号块有0,1两个元素
block[1] = 4,1号块有3,4,4,5这四个元素
block[2] = 1,2号块只有8这1个元素
table[0] = table[1] = table[3] = table[5] = table[8] = 1 都只有1个数
但是table[4] = 2,因为有两个4

然后找第K大的数,假设K是5,sum表示当前已经累计存在的数的个数,初始为0
遍历到0号块时,sum + block[0] = 0 + 2 = 2 < 5,所以第K大的数不在0号块,令sum为2
遍历1号块,sum + block[1] = 2 + 4 = 6 > 5,所以第K大的数在1号块内。
sum = 2,接下来遍历1号块内每个元素,即3,4,4,5
遍历到元素3时,sum = sum + table[3] = 3 < 4,所以3不是第K大的数
遍历到元素4时,sum = sum + table[4] = 5 > 4,因此找到4,即为第K大的数

方法应用:PAT甲级1057 Stack


本文链接: http://www.dtmao.cc/news_show_600388.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?