本文介绍: 在海量数据中,此时普通的数组、链表、Hash、树等等结构有无效了 ,因为内存空间放不下了。而常规的递归、排序,回溯、贪心和动态规划等思想也无效了,因为执行都会超时,必须另外想办法。这类问题该如何下手呢?
《算法通关村——位运算在查找重复元素中的妙用》
在海量数据中,此时普通的数组、链表、Hash、树等等结构有无效了 ,因为内存空间放不下了。而常规的递归、排序,回溯、贪心和动态规划等思想也无效了,因为执行都会超时,必须另外想办法。这类问题该如何下手呢?这里介绍三种非常典型的思路:
用 4KB 内存寻找重复元素
分析:本身是一道海量数据问题的热身题,如果去掉“只有4KB”的要求,我们可以先创建一个大小为N的数组,然后将这些数据放进来,但是整数最大为32000。如果直接采用数组存,则应该需要32000*4B=128KB的空间,而题目有4KB的内存限制,我们就必须先解决该如何存放的问题。
如果只有4KB的空间,那么只能寻址8*4*2^10个比特,这个值比32000要大的,因此我们可以创建32000比特的位向量(比特数组),其中一个比特位置就代表一个整数。
利用这个位向量,就可以遍历访问整个数组。如果发现数组元素是v,那么就将位置为v的设置为1,碰到重复元素,就输出一下。
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。