微网站与普通网站的区别,东莞黄页顺企网,天津综合网站建设商店,郑州做网站公司中看了博客园里一篇文章《一道腾讯前端试题#xff0c;谁来试试身手》#xff0c;正好以前了解过位图法#xff0c;确实不错。位图法适用于大规模数据#xff0c;但数据状态又不是很多的情况。通常是用来判断某个数据存不存在#xff0c;如可标记1为存在#xff0c;0为不存… 看了博客园里一篇文章《一道腾讯前端试题谁来试试身手》正好以前了解过位图法确实不错。位图法适用于大规模数据但数据状态又不是很多的情况。通常是用来判断某个数据存不存在如可标记1为存在0为不存在。 位图法网上资料比较少我在百度百科找到了对它的描述 位图法比较适合于如下这种情况它的做法是按照集合中最大元素max创建一个长度为max1的新数组然后再次扫描原数遇到几就给新数组的第几位置上1如遇到 5就给新数组的第六个元素置1这样下次再遇到5想置位时发现新数组的第六个元素已经是1了这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。 效率测试(参考一道腾讯前端试题谁来试试身手) 传统的双重循环查找也是可取的但效率实在不敢恭维特别是处理大量数据时候 class Program{static void Main(string[] args){//产生随机数int[] array Enumerable.Range(1, 100000).OrderBy
(n Guid.NewGuid()).Take(80000).ToArray();DateTime dt1 DateTime.Now;int max array[0];int flag;//数组无序排列查找最大值for (int i 1; i array.Length; i){if (array[i] max){max array[i];}}for (int i 1; i max; i){flag 1;for (int j 0; j array.Length; j){//相等标记Flag0,意味着不是缺少的数字if (i.Equals(array[j])){flag 0;break;}}if (flag 1){Console.Write({0},, i);}}DateTime dt2 DateTime.Now;TimeSpan ts dt2 - dt1;Console.WriteLine(\r\n 共耗时间{0}ms, ts.TotalMilliseconds);//52730.5525Console.ReadKey();}} 测试结果数据量小时还OK数据量大的情况下显示很卡很缓慢最坏的时间复杂度TnO(n*n) 以上测试总时间约为51291.2996MS 位图法测试 class Program{static void Main(string[] args){//随即产生80000个不重复数int[] array Enumerable.Range(1, 100000).OrderBy
(n Guid.NewGuid()).Take(80000).ToArray();//int[] array{1,2,3,5,7,9,10,12,45,62,55,78,98,52,12,4,200,60,63,65,66,67,68,69,70,74,79,80,82,89,90,91,92,93,94,98,100,101};DateTime dt1DateTime.Now;//找出最大值int maxarray[0];for (int i 1; i array.Length; i){if (array[i]max){max array[i];}}//新数组的长度为旧数组最大数字1int[] losenew int[max1];foreach (int item in array){//若Item为2,则Lose[2]1...所以新数组的长度为旧数组最大数字1lose[item] 1;}//那么为0的就是缺少值for (int i 1; i lose.Length; i)//100{if (lose[i].Equals(0)){Console.Write({0},,i);}}DateTime dt2DateTime.Now;Console.WriteLine(\r\n(dt2-dt1).TotalMilliseconds);//6004.3379MsConsole.ReadKey();}} 位图法在确定最大数值后的时间复杂度还是挺乐观的最坏情况TnO(2n) 屏幕飞快的刷新着测试时间约是6295.3601MS 总结 判断集合中是否存在重复元素或者查找缺失元素是常见编程任务之一当集合中数据量比较大时我们通常希望少进行几次扫描这时双重循环法就不可位图法Bitmap可以考虑。。 转载于:https://www.cnblogs.com/OceanEyes/archive/2012/07/12/bitmap_test.html
