JavaScript 数组中找出相同字符串元素_百度知道
JavaScript 数组中找出相同字符串元素
字符串A=&01,02,03,04,05,06|a1,a2,a3&字符串B=&03,05,07,09,10|a2,b1,b2,b3,b5&字符串中有两种分隔符
相同的字符串个数,
| 前的有几个相同,|后的有几个相同谢谢
答题抽奖
首次认真答题后
即可获得3次抽奖机会，100%中奖。
如果数组中个元素是字符串，这么做方便，如果不是，那就用@lyw_2008_happy的方法就行var&arr1&=&['a','b','c','d'];&var&arr2&=&['x','b','c','y'];var&long&=&arr1.length&arr2.length?arr2:arr1;var&short&=&arr1.length&arr2.length?arr1:arr2;var&str&=&","+long.toString()+",";var&result=[];for(var&i&in&short){&&&&if(str.indexOf(","+short[i]+",")&=0){&&&&&&&&result.push(short[i]);&&&&}}alert(result.toString());
采纳率：46%
为您推荐：
其他类似问题
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。16:56 提问
运用javascript如何去除数组中重复的数字或者字符串？
运用javascript如何去除数组中重复的数字或者字符串？谢谢了。方法越多越好，谢谢。
按赞数排序
----------------------同志你好，我是CSDN问答机器人小N，奉组织之命为你提供参考答案，编程尚未成功，同志仍需努力！
本人只会用JAVA写
准确详细的回答，更有利于被提问者采纳，从而获得C币。复制、灌水、广告等回答会被删除，是时候展现真正的技术了！
其他相关推荐{1,22,56,53,34,51,77}这是一个数组，如何不用内部函数和遍历数组的方法判断出 53 在这个数组里。（面试问题）
22:02:34 +08:00 · 8699 次点击
我想到了php中的in_array()函数。但是很明显不对。
119 回复 &| &直到
10:50:44 +08:00
& & 22:07:09 +08:00 via iPad
用查找算法？
& & 22:09:49 +08:00
用 implode 合并成逗号分隔的字符串，然后判断字符串？
任何 php 内部函数都不能用吗还是说仅仅不能用同功能的函数？
& & 22:13:31 +08:00
public static function inArray($item, $array) {
$flipArray = array_flip($array);
return isset($flipArray[$item]);
}
这个？？？
& & 22:18:13 +08:00
不用内部函数？那貌似只能一个一个去if($arr[0] == 53) 了。。
& & 22:20:04 +08:00
array_flip也是内部函数啊
& & 22:26:49 +08:00
应该就是考查找算法吧。
& & 22:39:37 +08:00
针对这个数组进行任何处理，都有可能进行遍历的吧！
如果不需要遍历，不如生成一个 0 到数组长度 -1 随机数，来随机读取数组内元素，每次保证不重复读取相同位置上就行了。这样有七分之一的概率不需要遍历数组。
& & 22:44:59 +08:00
不遍历怎么知道？？感觉这种问题怎么有点弱智啊。。。
& & 22:45:19 +08:00
赌10元钱任何实现都用到了某种程度上的遍历。
& & 22:46:04 +08:00
不管用什么方法到最后都是要遍历的，至少得知道里面有那些元素吧
除非能找到一个公式可以生成这个序列，不然不可能的
& & 22:51:38 +08:00 via Android
不让遍历的意思就是不让你逐个看这里面的东西吧。
PHP内部函数1500个都不让用，又不让看。
这是什么鬼？
& & 22:51:42 +08:00
@ 随机数生成，重复读取判断，这貌似增加复杂度了吧。数组本身无序，已经存在不需要遍历的可能性了吧。要是可接受近似解，貌似有个什么亚线性算法可以用，具体不知了
& & 22:52:20 +08:00 via iPhone
@ 那也是遍历啊
& & 22:53:02 +08:00
@ 不过这种题感觉就是考个遍历，传说中的 FuzzBuzz 测试
& & 22:55:06 +08:00
我们可以用in呀
---
好吧，上面开玩笑的，也是遍历，求正确姿势
& & 22:56:33 +08:00
@ 此方法，不错，忘记叫什么算法了，概率性很大。
& & 22:59:31 +08:00
@ 是蒙特卡洛么，有点这个的感觉
& & 23:02:39 +08:00
@ 不是，我记得当初的一个场景时，一个猴子为了排序3个大小不同的干果，不断的往天上抛，直到，排序正确位置，适用于少量元素排序，概率性很大。
& & 23:03:20 +08:00
$array = {1,22,56,53,34,51,77};
if (TRUE || array) {
echo '我灵光一闪，断定 53 必然在这个数组里。';
}
& & 23:04:48 +08:00
查找算法也是要遍历的呀
& & 23:11:25 +08:00 via Android
@ 构造随机数作为索引随机命中 如果匹配就。。。。。？
& & 23:13:32 +08:00
@ 感觉考察的是算法。但是我不也不会！
& & 23:14:05 +08:00
@ 应该是同功能的函数，比如in_array()
& & 23:14:22 +08:00
@ 文字上可以不叫遍历，本质上不也是挨着挨着一个一个问么。
& & 23:15:24 +08:00
@ 我感觉这个不是正确答案！
& & 23:18:46 +08:00
@ 我要是面试成功的话，我一定问问他这个答案，我很无语，查了很多资料，感觉是算法。
& & 23:20:35 +08:00
@ 大数据算法？感觉有点抽象！
& & 23:22:57 +08:00
@ 这个是个好思路，哈哈！
& & 23:23:18 +08:00
可以反证 必须要遍历的
& & 23:27:56 +08:00 via Android
@ @ 说的是模糊测试
see
& & 23:30:57 +08:00
@ 正解 某年acm切的題
如果特別考察你算法的話 翻翻拓撲的東西 以前數學課上過 現在記不清了
& & 23:31:46 +08:00
bool find1(int num, int index, int* arr)
{
return num == arr[index];
}
bool find3(int num, int base_index, int* arr)
{
return find1(num, base_index, arr) || find1(num, base_index + 1, arr) || find1(num, base_index + 2);
}
bool find6(int num, int base_index, int* arr)
{
return find3(num, base_index, arr) || find3(base_index + 4);
}
int main()
{
int arr[] = {1,22,56,53,34,51,77};
auto found = find1(53, arr) || find6(53, 1, arr);
& & 23:35:14 +08:00
随手写的， 有些typo
& & 23:37:13 +08:00
@ 我感觉他考的是效率或者算法。当时我还想到了二叉树，从中间分，log2N。（以前考计算机二级的时候学的，现在都忘了，不知道对不对，呵呵）
& & 23:39:11 +08:00 via Android
& & 23:42:34 +08:00 via Android
& & 23:42:47 +08:00
@ 你这好像没有遍历也没有内部函数，牛呀，但是我得抽空测试下，这个好像是C写的。
& & 23:46:15 +08:00
@ 如果数组有序，二分还可以
& & 23:46:34 +08:00
@ 我测试过了， 应该没错。
//====================
bool find1(int num, int index, int* arr){ return num == arr[index]; }
bool find3(int num, int base_index, int* arr){ return find1(num, base_index, arr) || find1(num, base_index + 1, arr) || find1(num, base_index + 2, arr); }
bool find6(int num, int base_index, int* arr){ return find3(num, base_index, arr) || find3(num, base_index + 4, arr); }
bool find7(int num, int* arr, size_t size){ return find1(num, 0, arr) || find6(num, 1, arr); }
int main()
{
int arr[] = {1,22,56,53,34,51,77};
auto found = find7(53, arr, sizeof(arr));
assert(found);
}
& & 23:46:40 +08:00
我觉得需要定义一下遍历。。。
& & 23:53:27 +08:00
@ 牛，崇拜！
& & 23:54:50 +08:00
array_flip
然后 array_key_exists
应该最快吧 ?
& & 23:58:21 +08:00
& & 23:59:37 +08:00
@ 这个用了php内部函数了，我感觉会快些，因为用数字查询比较吧，但是跟in_array()相比也没啥区别！
& & 00:01:35 +08:00
那个随机数的为什么不直接遍历前6个。。
这样也有七分之一的概率不需要遍历所有。。。
& & 00:02:37 +08:00
@ 这个方法好，我看了，可以，感觉递归有可能是正确答案，但是好像这也是一种遍历！
& & 00:05:33 +08:00
如果是面试 我觉得 递归和 array_flip
都应该算是正解 起码说得过去
& & 00:16:33 +08:00
递归算遍历吗？我只想到递归了。
& & 00:17:28 +08:00
以前我面试也被问了这个问题……实在想不出比遍历更快的方法，然后一直不知道答案
& & 00:29:16 +08:00 via iPhone
@ 基本上就是递归了。。。不过这个的递归想不到什么巧妙的方法。直接简单的递归太没意思了
& & 00:33:09 +08:00
请定义 遍历 。。。
如果说 ·遍历· 是指按照索引顺序的话，那当然是可以做到不用·遍历·。。。
& & 00:42:43 +08:00 via Android
如果说遍历是指完整的访问了每一个数，那么对于某些数，只访问其中的一部分二进制位（最少为 1 个位）是不是一种符合条件的解法？
比如说，用每个数的最低位与待查找数的最低位做位与，相同的挑出来，再比较次低位，以此类推。
对于这个题来说，如果是 int32 的数组，共 224 个 bit，读取了其中的 44 个 bit 之后确认了 53 的存在，仅仅访问了 19.6% 的数据，是不是不算是严格意义上的遍历呢。
当然实际情况下你只能按字节读取，即便这样也仅访问了 35.7% 的数据而已。
然并卵，你硬说它是遍历它确实也是。。。
& & 00:44:50 +08:00 via Android
递归是遍历的一种方法而已啊，类似遍历二叉树，可以有递归或者非递归的两种算法。这个题目用递归写本质上还是遍历了哇，并且占有内存上还比直接一个个读来的大= =
& & 01:03:10 +08:00
我觉得出题人是想考楼主手写排序和二分的，估计是题目没写清楚...
递归也算遍历，但是没办法，这个题不用遍历做不了
写了一个递归的：
$arr = [1, 22, 56, 53, 34, 51, 77];
function _find($arr, $search, $left, $right)
{
if ($left & $right)
$pivot = rand($left, $right);
return $arr[$pivot] == $search
: _find($arr, $search, $left, $pivot-1) || _find($arr, $search, $pivot+1, $right);
$found = _find($arr, 53, 0, count($arr)-1);
& & 01:34:10 +08:00 via Android
@ 思路不错，不过现在CPU cache都是64byte，你读int的一个字节等于读了整个int
& & 02:19:19 +08:00
不用遍历我也是笑了 这是数组不是hash 面试官傻逼别跟着一帮人 学过数据结构么？
& & 02:22:57 +08:00
建议楼主了解一下布隆过滤器
& & 05:20:14 +08:00
Bloom Filter的大致原理是 先 遍 历 一 次 计 算 得 到 HashSet
第二次通过索引HashSet直接命中目标元素 所以仍然无法避免 遍 历
see
我前面提到的方法：&构造随机数作为索引随机命中& 理论理想的情况下可以避免 遍历
@ PHP的array在Zend Engine的实现就是HashTable
see
& & 06:09:38 +08:00
@ 单给你一个数组哪来的bloom filter
@ 你这个跟遍历没有区别，期望值是一样的
& & 06:29:25 +08:00
hash table 不行？
& & 09:33:48 +08:00 via Android
53 不就在这个数组里吗，一眼就能看出来，实在要写就来个 return array[3] == 53
& & 10:32:21 +08:00
需求不明,你可以反问面试官几句
一帮助您正确理解题意
& & 11:00:02 +08:00
不可能没有遍历。。。看到有人说递归。。。递归不也是遍历。。。$i++。。
& & 11:50:31 +08:00
我觉得蒙特卡洛算法正解。
虽然这个算法的期望时间复杂度很高，但是来保证一定可以判断某个数字是否在array里。比如说我们把每次随机生成的下标保存在HashSet里，如果某次随机生成的下标已经在集合里我们就抛弃他。这样经过足够长的时间我们总能100%的确定53是不是在array里。（当集合size和array 的 size 相同的时候结束算法）。
& & 11:59:39 +08:00
搞不懂什么目的？
var a = [1, 2, 3, 4, 5, 6, 7];
console.log((',' + a.toString() + ',').indexOf(',3,') & 0);
转成字符串 用indexOf 算内部函数？
& & 12:48:00 +08:00
要求不遍历，就是二分查找了。二分查找 只有最差的情况才是遍历
排序 已经 遍历了。不遍历根本不能那个排序
& & 13:40:48 +08:00
@ +1 上面说的递归和字符串啥的，其实都算遍历的一种了
& & 13:47:20 +08:00
不让遍历无解， 那是魔术师干的事情。
& & 13:48:53 +08:00
就算是人工一眼看出53在里面， 也包含了目光的遍历。
& & 13:58:38 +08:00
& & 14:19:29 +08:00
感觉这个比较问题扯啊，明明是个简单的问题非要复杂化。
& & 14:23:50 +08:00
注意到53是素数所以全部乘起来再模53看是否等于0就好了
& & 14:25:20 +08:00
排序，二分？
& & 14:26:04 +08:00
@ 终于出现正确答案了。
& & 14:34:17 +08:00
你们打算怎样把数组全部乘起来?
& & 14:40:29 +08:00
53素数，全乘，摸53，判断是否为0
& & 14:40:42 +08:00
全部乘起来，不是得遍历一遍，取出数字相乘么？
相比较遍历一遍，取数比较，有什么优势
& & 14:43:48 +08:00 via iPad
本来遍历到一半就能确认的问题，非要遍历一遍算积再除
& & 14:45:28 +08:00
笑死人了，还tm正确答案，真不知道是不是高级黑……
& & 14:47:17 +08:00
这个肯定要遍历的啊，就算完全不懂编程好了，假设里面100个元素，使用某种手段访问了其中99个，发现没找到这个数字，那么剩下那个数字你是访问呢还是不访问呢
& & 15:02:34 +08:00
遇到这种公司，直接拜拜是最好的选择；要是进去了，还不知道会遇到什么213的产品经理呢，到那时就欲哭无泪了。
& & 15:26:32 +08:00
{1,22,56,53,34,51,77}这是一个数组 ( 这是已知条件)，
如何不用内部函数和遍历数组的方法判断出 53 在这个数组里。（这是问题）
答：function checkIf53Exist() {}
！！！！！！！！！ 重要 ！！！！！！！！！！！
已知条件里已经包含53了，又没有问你任意数组，你们还争论遍历和查找个毛啊，典型的审题不清。
都是程序猿思维，我要是考官，给我说算法的人，统统OUT。
& & 15:44:50 +08:00
怎么乘？当然是用计算器了，难不成口算？？！
function check_in_array($prime, $product) {return !($product % $prime);}
var_dump(check_in_array(53, ));
完美解决！
& & 15:46:25 +08:00
看那乘积，果然是大数据！
& & 15:57:21 +08:00
一般面试考这类东西都是考算法的。
所以这个题十有八九是让你给出一个时间复杂度小于O(n)的算法来找出某个元素。
有序数组，直接2分查找；
部分有序或者是循环有序数组，也是采用划分的思想，不过需要确定单调区间来决定每次查找的区间。
楼主给的这个数组感觉有问题啊。
& & 16:08:53 +08:00
@ 毕竟低学历，只是个自由职业者，真不知道哪来的自信。。。。。
& & 16:14:26 +08:00
毕竟写了8年PHP，这点自信还是有的哇哈哈哈
& & 16:20:35 +08:00
好无聊啊，大家都在说生成随机数然后判重
正确姿势难道不是生成一个len(array)的排列，然后按这个序号去访问么？生成排列有线程算法吧
& & 16:25:08 +08:00
@ 为了避免程序遍历整个数组，改为人工遍历整个数组。我怎么就没想到这么好的方法呢？
& & 16:35:18 +08:00
@ 好吧，我以为可以先对数组做预处理呢
& & 16:39:32 +08:00
数组转json，然后strpos
& & 16:47:16 +08:00
@ 对，人工遍历可以提高系统鲁棒性，比如停电什么的就不怕了
& & 16:47:31 +08:00
@ ...你让我心碎。。。的无以复加
& & 17:09:24 +08:00
转成字符串的本质也是遍历，如果这个也不可以的话，问题就转换成了薛定谔的猫：如何在不查看数组元素的办法猜里面是啥样
& & 17:25:45 +08:00
每一种方法都在遍历啊卧槽……
& & 17:27:50 +08:00
@ 赞同,检查每一个位.不过不知道出题人到底是啥意思
& & 17:41:36 +08:00
大小都没超过128，7个8bit的数位， 53-&
如果53在其中，则会有序数为8的整数倍开始的连续的8个0
所以目标是是检测是否有这样的
对XOR结果的第一第二字节 和第四第五字节 取AND操作，得到的结果和 （第三字节位码） 取AND操作，得到一个结果a
if !( a & b1111) || !(a & b0000)
则认为53在原始数组中， 瞎说的 不知道对不对
好像没遍历？
& & 17:43:18 +08:00
不遍历怎么乘起来
& & 17:54:38 +08:00
将 Array 转为 Set ,再记下集合里面元素的个数，然后添加 53 进去。如果集合里面元素个数多了一个，那么 53 不在里面；如果保持不变，那么在里面。（我瞎扯的）
& & 19:11:19 +08:00
难道没人知道 bloom filter？
& · & 1341 人在线 & 最高记录 3541 & · &
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.1 · 28ms · UTC 00:11 · PVG 08:11 · LAX 17:11 · JFK 20:11? Do have faith in what you're doing.设置两个临时变量t1，t2，然后遍历数组，t1始终保存较大值，t2保存较小值，遍历完毕，就能得到一个最大值t1，最小值t2。
是我想的太简单了，还是题就是这样？
一次遍历，找出最大值max、最小值min，最大差值 = max - min，时间复杂度O(n)。
冒泡算法，第一趟从前向后——倒数第一位最大的数，第二趟从倒数第二位向前——第一位为最小的数，最后一位减第一位。比较((n-1)+(n-2))次，比较O(2n)；最好情况换值0次（由小到大排好序的数组），最差情况换值((n-1)+(n-2))次，平均换值O(n)，复杂度O(3n)
用两次堆排序，第一次生成最大堆，得到最大值，第二次生成一个最小堆，得到最小值，时间复杂度是log(n)
public static void solution(int a[]) {
int min = 0;
int max = 0;
for (int i = 1; i & a. i++) {
if (a[i] & a[max])
else if (a[i] & a[min])
System.out.println(&the result is &+((a[max]-a[min])));
用快速排序将数组排好序后，找出最小，最大值
public static int findNumber(int []arr){
if(arr==null||arr.length==0){
int max=arr[0];
int min=arr[0];
for(int i=1;i&arr.i++){
if(arr[i]&max) max=arr[i];
if(arr[i]&min) min=arr[i];
return max=
//复杂度为O(n)
f(vector&int& v)
vmin=vmax=v[0];
for(int i=1;i&v.size();i++)
if(v[i]&vmax) vmax=v[i];
if(v[i]&vmin) vmin=v[i];
return abs(vmin-vmax);
public static int findTheNumber(int[] array) {
if(null == array || 0 == array.length) return 0;
int min = array[0], max = array[0];
for(int i = 1; i & array. i++) {
if(array[i] & max) {
max = array[i];
if(array[i] & min) {
min = array[i];
return max -
答：本题等同于找到该数组中最大值和最小值
int Find(int a[],int n)
if(a==NULL || n&1)
return -1;
int min=a[0];
int max=a[0];
for(int i=1;i&n;i++)
if(a[i]&max)
if(a[i]&min)
result=max-
//时间复杂度为O(n),n为数组元素的大小
这道题你会答吗？花几分钟告诉大家答案吧！
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
京ICP备号-4
扫一扫，把题目装进口袋阅读(25939)
& & & & 前两天面试3面学长问我的这个问题（想说TEG的3个面试学长都是好和蔼，希望能完成最后一面，各方面原因造成我无比想去鹅场的心已经按捺不住了），这个问题还是建立最小堆比较好一些。
& & & & 先拿10000个数建堆，然后一次添加剩余元素，如果大于堆顶的数（10000中最小的），将这个数替换堆顶，并调整结构使之仍然是一个最小堆，这样，遍历完后，堆中的10000个数就是所需的最大的10000个。建堆时间复杂度是O（mlogm），算法的时间复杂度为O（nmlogm）（n为10亿，m为10000）。
& & & & 优化的方法：可以把所有10亿个数据分组存放，比如分别放在1000个文件中。这样处理就可以分别在每个文件的10^6个数据中找出最大的10000个数，合并到一起在再找出最终的结果。
& & & & 以上就是面试时简单提到的内容，下面整理一下这方面的问题：
& & & & 在大规模数据处理中，经常会遇到的一类问题：在海量数据中找出出现频率最好的前k个数，或者从海量数据中找出最大的前k个数，这类问题通常被称为top K问题。例如，在搜索引擎中，统计搜索最热门的10个查询词；在歌曲库中统计下载最高的前10首歌等。
& & & & 针对top K类问题，通常比较好的方案是分治+Trie树/hash+小顶堆（就是上面提到的最小堆），即先将数据集按照Hash方法分解成多个小数据集，然后使用Trie树活着Hash统计每个小数据集中的query词频，之后用小顶堆求出每个数据集中出现频率最高的前K个数，最后在所有top K中求出最终的top K。
eg：有1亿个浮点数，如果找出期中最大的10000个？
& & & & 最容易想到的方法是将数据全部排序，然后在排序后的集合中进行查找，最快的排序算法的时间复杂度一般为O（nlogn），如快速排序。但是在32位的机器上，每个float类型占4个字节，1亿个浮点数就要占用400MB的存储空间，对于一些可用内存小于400M的计算机而言，很显然是不能一次将全部数据读入内存进行排序的。其实即使内存能够满足要求（我机器内存都是8GB），该方法也并不高效，因为题目的目的是寻找出最大的10000个数即可，而排序却是将所有的元素都排序了，做了很多的无用功。
& & & & 第二种方法为局部淘汰法，该方法与排序方法类似，用一个容器保存前10000个数，然后将剩余的所有数字——与容器内的最小数字相比，如果所有后续的元素都比容器内的10000个数还小，那么容器内这个10000个数就是最大10000个数。如果某一后续元素比容器内最小数字大，则删掉容器内最小元素，并将该元素插入容器，最后遍历完这1亿个数，得到的结果容器中保存的数即为最终结果了。此时的时间复杂度为O（n+m^2），其中m为容器的大小，即10000。
& & & & 第三种方法是分治法，将1亿个数据分成100份，每份100万个数据，找到每份数据中最大的10000个，最后在剩下的100*10000个数据里面找出最大的10000个。如果100万数据选择足够理想，那么可以过滤掉1亿数据里面99%的数据。100万个数据里面查找最大的10000个数据的方法如下：用快速排序的方法，将数据分为2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大堆个数N小于10000个，就在小的那堆里面快速排序一次，找第10000-n大的数字；递归以上过程，就可以找到第1w大的数。参考上面的找出第1w大数字，就可以类似的方法找到前10000大数字了。此种方法需要每次的内存空间为10^6*4=4MB，一共需要101次这样的比较。
& & & & 第四种方法是Hash法。如果这1亿个书里面有很多重复的数，先通过Hash法，把这1亿个数字去重复，这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间，然后通过分治法或最小堆法查找最大的10000个数。
& & & & 第五种方法采用最小堆。首先读入前10000个数来创建大小为10000的最小堆，建堆的时间复杂度为O（mlogm）（m为数组的大小即为10000），然后遍历后续的数字，并于堆顶（最小）数字进行比较。如果比最小的数小，则继续读取后续数字；如果比堆顶数字大，则替换堆顶元素并重新调整堆为最小堆。整个过程直至1亿个数全部遍历完为止。然后按照中序遍历的方式输出当前堆中的所有10000个数字。该算法的时间复杂度为O（nmlogm），空间复杂度是10000（常数）。
实际运行：
& & & & 实际上，最优的解决方案应该是最符合实际设计需求的方案，在时间应用中，可能有足够大的内存，那么直接将数据扔到内存中一次性处理即可，也可能机器有多个核，这样可以采用多线程处理整个数据集。
& & & &下面针对不容的应用场景，分析了适合相应应用场景的解决方案。
（1）单机+单核+足够大内存
& & & & 如果需要查找10亿个查询次（每个占8B）中出现频率最高的10个，考虑到每个查询词占8B，则10亿个查询次所需的内存大约是10^9 * 8B=8GB内存。如果有这么大内存，直接在内存中对查询次进行排序，顺序遍历找出10个出现频率最大的即可。这种方法简单快速，使用。然后，也可以先用HashMap求出每个词出现的频率，然后求出频率最大的10个词。
（2）单机+多核+足够大内存
& & & & 这时可以直接在内存总使用Hash方法将数据划分成n个partition，每个partition交给一个线程处理，线程的处理逻辑同（1）类似，最后一个线程将结果归并。
& & & & 该方法存在一个瓶颈会明显影响效率，即数据倾斜。每个线程的处理速度可能不同，快的线程需要等待慢的线程，最终的处理速度取决于慢的线程。而针对此问题，解决的方法是，将数据划分成c×n个partition（c&1），每个线程处理完当前partition后主动取下一个partition继续处理，知道所有数据处理完毕，最后由一个线程进行归并。
（3）单机+单核+受限内存
& & & & 这种情况下，需要将原数据文件切割成一个一个小文件，如次啊用hash(x)%M，将原文件中的数据切割成M小文件，如果小文件仍大于内存大小，继续采用Hash的方法对数据文件进行分割，知道每个小文件小于内存大小，这样每个文件可放到内存中处理。采用（1）的方法依次处理每个小文件。
（4）多机+受限内存
& & & & 这种情况，为了合理利用多台机器的资源，可将数据分发到多台机器上，每台机器采用（3）中的策略解决本地的数据。可采用hash+socket方法进行数据分发。
& & & & 从实际应用的角度考虑，（1）（2）（3）（4）方案并不可行，因为在大规模数据处理环境下，作业效率并不是首要考虑的问题，算法的扩展性和容错性才是首要考虑的。算法应该具有良好的扩展性，以便数据量进一步加大（随着业务的发展，数据量加大是必然的）时，在不修改算法框架的前提下，可达到近似的线性比；算法应该具有容错性，即当前某个文件处理失败后，能自动将其交给另外一个线程继续处理，而不是从头开始处理。
& & & & top K问题很适合采用MapReduce框架解决，用户只需编写一个Map函数和两个Reduce 函数，然后提交到Hadoop（采用Mapchain和Reducechain）上即可解决该问题。具体而言，就是首先根据数据值或者把数据hash(MD5)后的值按照范围划分到不同的机器上，最好可以让数据划分后一次读入内存，这样不同的机器负责处理不同的数值范围，实际上就是Map。得到结果后，各个机器只需拿出各自出现次数最多的前N个数据，然后汇总，选出所有的数据中出现次数最多的前N个数据，这实际上就是Reduce过程。对于Map函数，采用Hash算法，将Hash值相同的数据交给同一个Reduce
task；对于第一个Reduce函数，采用HashMap统计出每个词出现的频率，对于第二个Reduce 函数，统计所有Reduce task，输出数据中的top K即可。
& & & & 直接将数据均分到不同的机器上进行处理是无法得到正确的结果的。因为一个数据可能被均分到不同的机器上，而另一个则可能完全聚集到一个机器上，同时还可能存在具有相同数目的数据。
以下是一些经常被提及的该类问题。
（1）有个记录，这些查询串的重复度比较高，如果除去重复后，不超过3000000个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请统计最热门的10个查询串，要求使用的内存不能超过1GB。
（2）有10个文件，每个文件1GB，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。按照query的频度排序。
（3）有一个1GB大小的文件，里面的每一行是一个词，词的大小不超过16个字节，内存限制大小是1MB。返回频数最高的100个词。
（4）提取某日访问网站次数最多的那个IP。
（5）10亿个整数找出重复次数最多的100个整数。
（6）搜索的输入信息是一个字符串，统计300万条输入信息中最热门的前10条，每次输入的一个字符串为不超过255B，内存使用只有1GB。
（7）有1000万个身份证号以及他们对应的数据，身份证号可能重复，找出出现次数最多的身份证号。
& & & & 在海量数据中查找出重复出现的元素或者去除重复出现的元素也是常考的问题。针对此类问题，一般可以通过位图法实现。例如，已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。
& & & & 本题最好的解决方法是通过使用位图法来实现。8位整数可以表示的最大十进制数值为。如果每个数字对应于位图中一个bit位，那么存储8位整数大约需要99MB。因为1B=8bit，所以99Mbit折合成内存为99/8=12.375MB的内存，即可以只用12.375MB的内存表示所有的8位数电话号码的内容。
版权声明：本文为博主原创文章，未经博主允许不得转载。
阅读排行榜