给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
else if(this[i]
var blen=maxv-minv+1;
var b=new Array(blen);
for(var i=0;i
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
}
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;i
key=hashFun(value);
bucket = hashSet[key];
openLen=bucket.length;//if(openLen>1)return;
everConflict=false;
for(var j=0;j
ret.push(value);
everConflict=true;
break;
}
}
if(!everConflict){
bucket.push(value);
self.push(value);
}
}
selfLen = self.length;
this.length = selfLen;
for (i=0; i
}
//compute average bucket size
var lens=[],sum=0;
for(var i=0;i
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

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

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

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

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

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

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

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

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


热AI工具

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

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

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

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

热门文章

热工具

适用于 Eclipse 的 SAP NetWeaver 服务器适配器
将Eclipse与SAP NetWeaver应用服务器集成。

Dreamweaver Mac版
视觉化网页开发工具

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

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

WebStorm Mac版
好用的JavaScript开发工具