admin管理员组文章数量:1328776
In class today we were asked to write an algorithm.
Given an array, remove duplicate values:
- It should be stable, and shouldn't have to use an inner loop.
- Should be done in place, as best as possible
- No use of built in functions (I was only allowed to use
.push
)
After wrestling with it for a while, this is what I came up with.
function remove_dupes(arr){
var seen = {};
var count = 0;
for( var i = 0; i < arr.length - count ; i++) {
arr[i] = arr[i+count];
if( seen[arr[i]] ) {
count++;
arr[i] = arr[i+count];
i--;
}
seen[arr[i]] = true;
}
arr.length = arr.length - count;
}
Working JSBin
I have a bit of repeated code here and I feel that maybe the i--
isn't the best way to go.
Is there any way I could improve this code (without using built in functions)?
In class today we were asked to write an algorithm.
Given an array, remove duplicate values:
- It should be stable, and shouldn't have to use an inner loop.
- Should be done in place, as best as possible
- No use of built in functions (I was only allowed to use
.push
)
After wrestling with it for a while, this is what I came up with.
function remove_dupes(arr){
var seen = {};
var count = 0;
for( var i = 0; i < arr.length - count ; i++) {
arr[i] = arr[i+count];
if( seen[arr[i]] ) {
count++;
arr[i] = arr[i+count];
i--;
}
seen[arr[i]] = true;
}
arr.length = arr.length - count;
}
Working JSBin
I have a bit of repeated code here and I feel that maybe the i--
isn't the best way to go.
Is there any way I could improve this code (without using built in functions)?
Share Improve this question edited Sep 10, 2015 at 20:18 ahnkee asked Sep 10, 2015 at 19:24 ahnkeeahnkee 14510 bronze badges 2- I actually think the code looks pretty good as written. It's hard to write in-place code that looks anywhere near as neat as solutions that work on immutable objects. – ivern Commented Sep 10, 2015 at 19:44
- Thanks for your feedback. I'm pretty early in my course so they're drilling the basics/fundamentals as much as possible into us. My intuition hasn't developed to a point where I can look at something and know if it's an optimal solution on my own, so SO has been a great help – ahnkee Commented Sep 10, 2015 at 20:15
5 Answers
Reset to default 7Finally, I think I got what you want without creating a new array:
function remove_dupes(arr){
var seen = {};
var k = 0;
for( var i=0; i<arr.length ;i++) {
if( !seen[arr[i]] ) {
arr[k++] = arr[i];
seen[arr[i]] = 'seen';
}
}
arr.length = k;
}
var x = [ 1, 2, 1, 4, 5, 3, 'dojo', 4, 6, 6, 7, 7, 6, 7, 5, 6, 6, 6, 6, 7, 'dojo', 11 ];
remove_dupes(x);
document.write(x);
Hope it helps.
This seems like a simpler solution to me:
function remove_dupes(arr){
var seen = {};
var dupes_removed = [];
for( var i = 0; i < arr.length; i++) {
if (!seen[arr[i]]) {
dupes_removed.push(arr[i]);
seen[arr[i]] = true;
}
}
return dupes_removed;
}
This runs in somewhere between O(n) and O(nlogn) time (because JS hash lookups are between O(1) and O(logn) time). This also guarantees the result will be stable. The other solutions so far either run in O(n^2) or aren't stable.
You can use indexOf to see if that value exists in arr than push to a new one
function remove_dupes(arr){
var newArr = [];
for( var i = 0; i < arr.length; i++){
if(newArr.indexOf(arr[i]) === -1){
newArr.push(arr[i]);
}
}
return newArr;
}
var myArr = [2,4,2,4,6,6,6,2,2,1,10,33,3,4,4,4];
console.log(remove_dupes(myArr));
You can use Array.prototype.splice
to change the array in place (fiddle - look at the console):
var arr = [1, 54, 5, 3, 1, 5, 20, 1, 54, 54];
var seen = {};
var length = arr.length;
var i = 0;
while (i < length) {
if (seen[arr[i]] !== undefined) {
arr.splice(i, 1);
length--;
} else {
seen[arr[i]] = true;
}
i++;
}
console.log(arr);
This is O(n^2) as splice is O(n), and we iterate n elements.
This is a pact solution I am using in my JS array subclass:
if ( !Array.unique )
{
Array.prototype.unique = function()
{
var tmp = {}, out = [], _i, _n ;
for( _i = 0, _n = this.length; _i < _n; ++_i )
if(!tmp[this[_i]]) { tmp[this[_i]] = true; out.push(this[_i]); }
return out;
}
}
本文标签: Remove duplicates algorithmin place and stable (javascript)Stack Overflow
版权声明:本文标题:Remove duplicates algorithm, in place and stable (javascript) - Stack Overflow 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.betaflare.com/web/1742233591a2437668.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论