搜索
首页web前端js教程JavaScript 数组的 uniq 方法_javascript技巧

给Array本地对象增加一个原型方法,它的用途是删除数组条目中重复的条目(可能有多个),返回值是一个包含被删除的重复条目的新数组。

形式化描述:
input
Array(size=N)
output
Array1=Array的无重复保序的子集,
无重复是指,对任意a,b属于Array1,a!=b
保序是指,若a在Array的下标小于b在Array的下标,则a在Array1中的下标也小于b在Array的下标
Array2=Array-Array1,保序
realazy给出了一个新解,思路非常清晰:顺序遍历访问每个元素,如果这个元素的值已经访问过了,则加入Array2,否则加入Array1。判断当前元素的值是否已经访问过所采用的方法是顺序遍历已经访问过的所有元素。 
易见该算法复杂度约O(N^2)。

我在他的算法框架下稍微做了一些改进,关键在于遍历过程中如何判断当前元素的值是否已经访问过。在原数组值域为正整数且极差(range=max value-min value)不太大的条件下,可以采用简单的"桶"算法。
准备一个长度为range的boolean数组b,初始化全为false。对于原数组中每个值value,如果b[value]=true,则表明这个值访问过,放入Array2,否则放入Array1同时令b[value]=true。 
这显然是O(N)的算法,代价是额外的空间复杂度range,而且要求原数组值域为正整数。
不难推广到值域为整数的情形,事实上只需考察桶号value-min(Array)即可转化为正整数的情形。

为了避免range太大造成的空间的浪费,在"桶"算法基础上改进为散列算法,具体说来是线性同余开散列法。目的是将值域压缩映射到一个可控的小的连续正整数子集中,同时保证不同的原象对应的相同的象的概率要尽可能小,也就是说桶与桶之间要尽量负载均衡。 
例如这是一个值域为实数的散列函数:
key=hashFun(value)=Math.floor(value)*37%91
这仍然是O(N)的算法,(显然O(N)是所有uniq算法的复杂度下界),好处是可以控制空间的开销,而且可以适应非整数值域,只需要设计相应的散列函数即可。



下面是桶(bucket)算法的实现:
   var resultArr = [],
       returnArr = [], 
       origLen = this.length,
       resultLen;
   var maxv=this[0],minv=this[0];
   for (var i=1; i       if(this[i]>maxv)maxv=this[i];
       else if(this[i]   }
   var blen=maxv-minv+1;
   var b=new Array(blen);
   for(var i=0;i   for (var i=0; i       if (b[this[i]-minv]){
           returnArr.push(this[i]); 
       } else {
           resultArr.push(this[i]);
           b[this[i]-minv]=true;
       }
   }
   resultLen = resultArr.length;
   this.length = resultLen;
   for (var i=0; i       this[i] = resultArr[i];
   }
   return returnArr;
下面是散列(hash)算法的实现
var shuffler = 37
var beta=0.007;
var origLen=this.length
var bucketSize=Math.ceil(origLen*beta);
var hashSet=new Array(bucketSize); 
var hashFun = function(value){
var key = (Math.floor(value)*shuffler)%bucketSize;
return key;
}
//init hashSet
for(var i=0;i//
var ret=[],self=[];
var key,value; 
var bucket,openLen;
var everConflict;
for(var i=0;ivalue=this[i];
key=hashFun(value);
bucket = hashSet[key];
openLen=bucket.length;//if(openLen>1)return;
everConflict=false; 
for(var j=0;j if(bucket[j]==value){
  ret.push(value);
  everConflict=true;
  break;
 }
}
if(!everConflict){
 bucket.push(value);
 self.push(value);
}
}
   selfLen = self.length;
   this.length = selfLen;
   for (i=0; i       this[i] = self[i];
   }
//compute average bucket size
var lens=[],sum=0;
for(var i=0;iaverage=sum/hashSet.length;//watch lens,average
   return ret;


用k*10000个0~k*100的随机整数测试计算时间(ms)
k 1 2 3 4 5
realazy 240 693 1399 2301 3807 
bucket 55 101 141 219 293
hash 214 411 654 844 1083
测试框架借鉴了http://realazy.org/lab/uniq.html
测试环境Firefox2.0.0.6/Ubuntu7.10/2.66GHzP4/1024MBDDR 

声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
C和JavaScript:连接解释C和JavaScript:连接解释Apr 23, 2025 am 12:07 AM

C 和JavaScript通过WebAssembly实现互操作性。1)C 代码编译成WebAssembly模块,引入到JavaScript环境中,增强计算能力。2)在游戏开发中,C 处理物理引擎和图形渲染,JavaScript负责游戏逻辑和用户界面。

从网站到应用程序:JavaScript的不同应用从网站到应用程序:JavaScript的不同应用Apr 22, 2025 am 12:02 AM

JavaScript在网站、移动应用、桌面应用和服务器端编程中均有广泛应用。1)在网站开发中,JavaScript与HTML、CSS一起操作DOM,实现动态效果,并支持如jQuery、React等框架。2)通过ReactNative和Ionic,JavaScript用于开发跨平台移动应用。3)Electron框架使JavaScript能构建桌面应用。4)Node.js让JavaScript在服务器端运行,支持高并发请求。

Python vs. JavaScript:比较用例和应用程序Python vs. JavaScript:比较用例和应用程序Apr 21, 2025 am 12:01 AM

Python更适合数据科学和自动化,JavaScript更适合前端和全栈开发。1.Python在数据科学和机器学习中表现出色,使用NumPy、Pandas等库进行数据处理和建模。2.Python在自动化和脚本编写方面简洁高效。3.JavaScript在前端开发中不可或缺,用于构建动态网页和单页面应用。4.JavaScript通过Node.js在后端开发中发挥作用,支持全栈开发。

C/C在JavaScript口译员和编译器中的作用C/C在JavaScript口译员和编译器中的作用Apr 20, 2025 am 12:01 AM

C和C 在JavaScript引擎中扮演了至关重要的角色,主要用于实现解释器和JIT编译器。 1)C 用于解析JavaScript源码并生成抽象语法树。 2)C 负责生成和执行字节码。 3)C 实现JIT编译器,在运行时优化和编译热点代码,显着提高JavaScript的执行效率。

JavaScript在行动中:现实世界中的示例和项目JavaScript在行动中:现实世界中的示例和项目Apr 19, 2025 am 12:13 AM

JavaScript在现实世界中的应用包括前端和后端开发。1)通过构建TODO列表应用展示前端应用,涉及DOM操作和事件处理。2)通过Node.js和Express构建RESTfulAPI展示后端应用。

JavaScript和Web:核心功能和用例JavaScript和Web:核心功能和用例Apr 18, 2025 am 12:19 AM

JavaScript在Web开发中的主要用途包括客户端交互、表单验证和异步通信。1)通过DOM操作实现动态内容更新和用户交互;2)在用户提交数据前进行客户端验证,提高用户体验;3)通过AJAX技术实现与服务器的无刷新通信。

了解JavaScript引擎:实施详细信息了解JavaScript引擎:实施详细信息Apr 17, 2025 am 12:05 AM

理解JavaScript引擎内部工作原理对开发者重要,因为它能帮助编写更高效的代码并理解性能瓶颈和优化策略。1)引擎的工作流程包括解析、编译和执行三个阶段;2)执行过程中,引擎会进行动态优化,如内联缓存和隐藏类;3)最佳实践包括避免全局变量、优化循环、使用const和let,以及避免过度使用闭包。

Python vs. JavaScript:学习曲线和易用性Python vs. JavaScript:学习曲线和易用性Apr 16, 2025 am 12:12 AM

Python更适合初学者,学习曲线平缓,语法简洁;JavaScript适合前端开发,学习曲线较陡,语法灵活。1.Python语法直观,适用于数据科学和后端开发。2.JavaScript灵活,广泛用于前端和服务器端编程。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

适用于 Eclipse 的 SAP NetWeaver 服务器适配器

适用于 Eclipse 的 SAP NetWeaver 服务器适配器

将Eclipse与SAP NetWeaver应用服务器集成。

Dreamweaver Mac版

Dreamweaver Mac版

视觉化网页开发工具

SublimeText3 英文版

SublimeText3 英文版

推荐:为Win版本,支持代码提示!

螳螂BT

螳螂BT

Mantis是一个易于部署的基于Web的缺陷跟踪工具,用于帮助产品缺陷跟踪。它需要PHP、MySQL和一个Web服务器。请查看我们的演示和托管服务。

WebStorm Mac版

WebStorm Mac版

好用的JavaScript开发工具