logo标签列表

使用JavaScript从数组中删除重复对象

javascriptarraysalgorithmsorting
21

我正在尝试找出一种有效的方法来从数组中删除重复的对象，并寻找最有效的答案。我在互联网上搜索了一下，发现所有的方法好像都使用基本数据类型... 对于大型数组来说并不可扩展。这是我的当前实现方式，可以进行改进，我想尝试避免使用标签。

 Test.prototype.unique = function (arr, artist, title, cb) {
        console.log(arr.length);
        var n, y, x, i, r;
        r = [];      
        o: for (i = 0, n = arr.length; i < n; i++) {

          for (x = 0, y = r.length; x < y; x++) {

                if (r[x].artist == arr[i].artist && r[x].title == arr[i].title) {
                    continue o;
                }
            }
            r.push(arr[i]);
        }

        cb(r);
    };

数组看起来像这样：

[{title: sky, artist: jon}, {title: rain, artist: Paul}, ....]

顺序不重要，但如果排序可以使其更有效率，那我愿意挑战一下...

对于不了解 o 是一个标签的人，它只是表示跳回循环而不是推送到新数组。

请使用纯JavaScript，不使用库。

迄今为止的答案：

以下是性能测试的结果: http://jsperf.com/remove-duplicates-for-loops

你的_对象_对_JSON安全吗？将它们转换为字符串并进行比较可能是最快的方法。编辑这种方法可能不适合你，因为只有在属性按相同顺序定义时才有效。 - Paul S.
也许这个问题：https://dev59.com/T3A65IYBdhLWcg3wyh57 - todd.pund
使用jQuery！jQuery.unique（array）....... 哈哈 :) 但说真的，如果您想要，可以引用源代码，并查看它们如何处理它。 - Casey ScriptFu Pharr
@Casey 如果你期望不同的引用，那么这不适用于非基元类型。 - Paul S.
保罗，数据看起来就像那样，但有数千个对象，一些是重复的，属性都是有序的，但我更喜欢一个更通用的解决方案。 - Lion789
显示剩余4条评论
9个回答
30

我明白了，问题在于复杂度是平方级别的。有一个技巧可以解决这个问题，那就是使用“关联数组”。

你可以获取数组，循环遍历它，并将数组的值作为关联数组的键添加。由于它不允许重复的键，因此你会自动摆脱重复项。

由于你在进行比较时要查找标题和艺术家，所以你实际上可以尝试使用类似于：

var arrResult = {};
for (i = 0, n = arr.length; i < n; i++) {
    var item = arr[i];
    arrResult[ item.title + " - " + item.artist ] = item;
}

然后你只需要再次遍历arrResult，并重新创建数组。

var i = 0;
var nonDuplicatedArray = [];    
for(var item in arrResult) {
    nonDuplicatedArray[i++] = arrResult[item];
}

更新以包括 Paul 的评论。谢谢！

1
这里的 arrResult 是一个普通的 Object 对象。你还需要一个分隔符来保护 foo, bar，以免被 foob, ar 误解。+1，因为这对 OP 的情况应该很有效。 - Paul S.
不要忘记在循环之前声明'arrResult'，并使用arr[i]而不是内部的arr。 - Mike Edwards
它应该返回数组Result（你可以看到每个都是唯一的），但它只返回其中一个对象... - Lion789
2
@Lion789 这是你代码中的问题 - 你使用 title 和 artist 设置了 arrResult，但是你的示例数组有 key1 和 key2。http://jsfiddle.net/yKwZe/1/ - Scott Mermelstein
1
请为像我这样的初学者添加以下代码行：var nonDuplicatedArray = [];感谢您！在此提醒下，这个代码可以很好地工作。 - Sevak Avakians
显示剩余8条评论
3
这是一个对我有效的解决方案。
辅助函数：
// sorts an array of objects according to one field
// call like this: sortObjArray(myArray, "name" );
// it will modify the input array
sortObjArray = function(arr, field) {
    arr.sort(
        function compare(a,b) {
            if (a[field] < b[field])
                return -1;
            if (a[field] > b[field])
                return 1;
            return 0;
        }
    );
}

// call like this: uniqueDishes = removeDuplicatesFromObjArray(dishes, "dishName");
// it will NOT modify the input array
// input array MUST be sorted by the same field (asc or desc doesn't matter)
removeDuplicatesFromObjArray = function(arr, field) {
    var u = [];
    arr.reduce(function (a, b) {
        if (a[field] !== b[field]) u.push(b);
        return b;
    }, []);
    return u;
}

然后只需要调用：

        sortObjArray(dishes, "name");
        dishes = removeDuplicatesFromObjArray(dishes, "name");
3
我是这种解决方案的粉丝。谢谢！ - DrewT
2

这是一个基本的排序去重实现，可在此处进行调试:

function unique(arr) {
    var comparer = function compareObject(a, b) {
        if (a.title == b.title) {
            if (a.artist < b.artist) {
                return -1;
            } else if (a.artist > b.artist) {
                return 1;
            } else {
                return 0;
            }
        } else {
            if (a.title < b.title) {
                return -1;
            } else {
                return 1;
            }
        }
    }

    arr.sort(comparer);
    console.log("Sorted: " + JSON.stringify(arr));
    for (var i = 0; i < arr.length - 1; ++i) {
        if (comparer(arr[i], arr[i+1]) === 0) {
            arr.splice(i, 1);
            console.log("Splicing: " + JSON.stringify(arr));
        }
    }
    return arr;
}

这可能是最有效的，也可能不是，而且应该是完全可扩展的。我添加了一些console.log以便您在其工作时查看它。

编辑

为了节省函数使用的空间，我在结尾处进行了那个for循环，但似乎很可能没有正确地找到唯一的结果（尽管它通过了我的简单的jsfiddle测试）。请尝试用以下内容替换我的for循环：

var checker;
var uniqueResults = [];
for (var i = 0; i < arr.length; ++i) {
    if (!checker || comparer(checker, arr[i]) != 0) {
        checker = arr[i];
        uniqueResults.push(checker);
    }
}
return uniqueResults;
你可以查看https://dev59.com/ZXVC5IYBdhLWcg3woCnN#236534了解`sort`的典型复杂度信息。这显然会进行一个额外的线性遍历以使其唯一，并且不会明显占用任何额外空间。 - Scott Mermelstein
1
@Lion789 我同意。实际上我已经点赞了Henrique的答案，它是O(n)的，但我认为留下我的答案也无妨。它可能会在某一天对其他人有所帮助。 - Scott Mermelstein
@Lion789 这是你代码中的问题 - 你使用 title 和 artist 设置了 arrResult，但是你的示例数组有 key1 和 key2。 - Scott Mermelstein
啊 kk，好的，它不再是 off by one 了，这里更新了 http://jsfiddle.net/yKwZe/4/ - Lion789
1
@Lion789 http://jsfiddle.net/9TcQF/1/ 你没有对数组进行排序，也没有调用“unique”函数。现在已经修复了这两个问题，我们又可以得到4个结果了。 - Scott Mermelstein
显示剩余5条评论
1
以下是Henrique Feijo的答案，附有详细解释和可剪切粘贴的示例：
目标：将包含重复对象的对象数组（如此示例）转换为...
（注：原文中未提供具体内容，故无法进行翻译。）
[
    {
        "id": 10620,
        "name": "Things to Print"
    },
    {
        "id": 10620,
        "name": "Things to Print"
    },
    {
        "id": 4334,
        "name": "Interesting"
    }
]

将其转换为一个对象数组，不包含重复的对象（如此示例）：
[
    {
        "id": 10620,
        "name": "Things to Print"
    },
    {
        "id": 4334,
        "name": "Interesting"
    }
]

在注释中提供了解释：

    var allContent = [{
      "id": 10620,
      "name": "Things to Print"
    }, {
      "id": 10620,
      "name": "Things to Print"
    }, {
      "id": 4334,
      "name": "Interesting"
    }]

     //Put Objects Into As Associative Array. Each key consists of a composite value generated by each set of values from the objects in allContent.
    var noDupeObj = {} //Create an associative array. It will not accept duplicate keys.
    for (i = 0, n = allContent.length; i < n; i++) {
      var item = allContent[i]; //Store each object as a variable. This helps with clarity in the next line.
      noDupeObj[item.id + "|" + item.name] = item; //This is the critical step.
      //Here, you create an object within the associative array that has a key composed of the two values from the original object. 
      // Use a delimiter to not have foo+bar handled like fo+obar
      //Since the associative array will not allow duplicate keys, and the keys are determined by the content, then all duplicate content are removed. 
      //The value assigned to each key is the original object which is along for the ride and used to reconstruct the list in the next step.
    }

     //Recontructs the list with only the unique objects left in the doDupeObj associative array
    var i = 0;
    var nonDuplicatedArray = [];
    for (var item in noDupeObj) {
      nonDuplicatedArray[i++] = noDupeObj[item]; //Populate the array with the values from the noDupeObj.
    }

    console.log(nonDuplicatedArray)

1

对于喜欢ES6和简短内容的人，这里有一个解决方案：

const arr = [
  { title: "sky", artist: "Jon" },
  { title: "rain", artist: "Paul" },
  { title: "sky", artist: "Jon" }
];

Array.from(arr.reduce((a, o) => a.set(o.title, o), new Map()).values());


const arr = [
  { title: "sky", artist: "Jon" },
  { title: "rain", artist: "Paul" },
  { title: "sky", artist: "Jon" },
  { title: "rain", artist: "Jon" },
  { title: "cry", artist: "Jon" }
];

const unique = Array.from(arr.reduce((a, o) => a.set(o.title, o), new Map()).values());

console.log(`New array length: ${unique.length}`)

console.log(unique)

上面的例子仅适用于唯一的title或id。基本上，它为具有重复标题的歌曲创建了一个新地图。
1

我使用这个函数。它不会进行任何排序，但可以产生结果。无法确定其性能，因为从未对其进行过测量。

var unique = function(a){
    var seen = [], result = [];
    for(var len = a.length, i = len-1; i >= 0; i--){
        if(!seen[a[i]]){
            seen[a[i]] = true;
            result.push(a[i]);
        }
    }
    return result;
}

var ar = [1,2,3,1,1,1,1,1,"", "","","", "a", "b"]; console.log(unique(ar));// 这将会产生[1,2,3,"", "a", "b"]所有唯一的元素。

0
下面的代码将对象与JSON作为字符串格式进行比较，并去除重复项，在简单数组中运行良好。
    Array.prototype.unique=function(a){
     return function(){
        return this.filter(a)
     }
   }(
   function(a,b,c){
     var tmp=[]; 
     c.forEach(function(el){
        tmp.push(JSON.stringify(el))
    }); 
    return tmp.indexOf(JSON.stringify(a),b+1)<0
  })
我理解为什么没有人真正尝试使用它。或者至少给一些反馈。 - Jay
0
0
function remove_duplicates(objectsArray) {
    var arr = [], collection = []; 
    $.each(objectsArray, function (index, value) {
        if ($.inArray(value.id, arr) == -1) { 
            arr.push(value.id);
            collection.push(value);
        }
    });
    return collection;
}
O(N^2) 让小猫咪哭泣。 - Alexander
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接