从 Javascript 数组中删除等效但唯一的对象

Question

我有一个类似于以下的对象数组：

var routeArr = [
    {start: 1, end: 2},
    {start: 1, end: 3},
    {start: 1, end: 4},
    {start: 2, end: 1},
    {start: 3, end: 1},
    {start: 4, end: 1}
];

这些对象代表线的起点和终点，因此，{start: 1, end: 2} 和 {start: 2, end: 1} 代表同一条线。

我正在尝试从数组中删除所有重复的行，但找不到有效或优雅的方法来执行此操作。我已经尝试过嵌套循环，但有人告诉我这是不好的做法（而且我的实现出现错误，而且很丑陋）。

for(var i = 0, numRoutes = routeArr.length; i < numRoutes; i++) {
    var primaryRoute = routeArr[i];

    for(var j = 0; j < numRoutes; j++) {
        var secondRoute = routeArr[j];

        if(primaryRoute.start === secondRoute.end && primaryRoute.end === secondRoute.start) {
            routeArr.splice(j, 1);
            continue;
        }
    }
}

有人可以提供建议吗？

Answer 1

在javascript中创建一个object/map并保留唯一对象的索引，将"min(start,end):max(start,end)"存储为键，将索引存储为值。这是 javascript:

中你的问题的实现

// your initial array
var routeArr = [
    {start: 1, end: 2},
    {start: 1, end: 3},
    {start: 1, end: 4},
    {start: 2, end: 1},
    {start: 3, end: 1},
    {start: 4, end: 1}
];

// map where we will store key => value where key is a joined start,end of your array's item and value is an item index 
var keyToRouteIndexMap = {};

for (var i in routeArr){
    // calculating min and max from start and end to understand {start:1, end:2} and {start:2, end:1} object as duplicates
    var min = Math.min(routeArr[i].start,routeArr[i].end);
    var max = Math.max(routeArr[i].start,routeArr[i].end);
    // unique key 
    var key = min+':'+max;
    if (!keyToRouteIndexMap.hasOwnProperty(key)){
        keyToRouteIndexMap[key] = i;
    }
}

for(var key in keyToRouteIndexMap){
    if(keyToRouteIndexMap.hasOwnProperty(key)){
        console.log(routeArr[keyToRouteIndexMap[key]]);
    }
}

Answer 2

这是从 javascript 数组中删除重复值问题的一般解决方案：

/**
 * Takes an input array and returns a new array without identical elements.
 *
 * @param {array} input
 * @callback id   identity function returning identical values for identical elements
 */
function uniquify(input, id) {
    result = [];
    map = {};
    for (var i = 0, length = input.length; i < length; ++i) {
        var element = input[i], identity = id(element);
        if (!map.hasOwnProperty(identity)) {
            result.push(element);
            map[identity] = true;
        }
    }
    return result;
}

应用于您给定的routeArr：

var routeArr = [
    {start: 1, end: 2},
    {start: 1, end: 3},
    {start: 1, end: 4},
    {start: 2, end: 1},
    {start: 3, end: 1},
    {start: 4, end: 1}
];

routeArr = uniquify(routeArr, function(route) {
    return route.start < route.end ? '' + route.start + ':' + route.end : '' + route.end + ':' + route.start;
});

Answer 3

你可以这样做。我想这是非常快的，因为根本没有搜索。一个 Array.prototype.reduce() 操作同时构造散列 table（查找 table）和缩减对象。然后映射对象键得到结果。在这里;

var routeArr = [
    {start: 1, end: 2},
    {start: 1, end: 3},
    {start: 1, end: 4},
    {start: 2, end: 1},
    {start: 3, end: 1},
    {start: 4, end: 1}
],

reduced = routeArr.reduce((p,c) => {!(p[c.start+"-"+c.end] || p[c.end+"-"+c.start]) && (p[c.start+"-"+c.end] = c);
                                     return p;},{}),
 result = Object.keys(reduced).map(e => reduced[e]);
console.log(result);

好吧，再考虑一下，我删除了多余的 Object.keys() 部分。现在这只不过是一次 Array.prototype.reduce() 的传递，所有这些都在 O(n) 内完成。我想这可能是就性能而言。看看吧。

var routeArr = [
    {start: 1, end: 2},
    {start: 1, end: 3},
    {start: 1, end: 4},
    {start: 2, end: 1},
    {start: 3, end: 1},
    {start: 4, end: 1}
],

     reduced = routeArr.reduce((p,c) => {!(p[c.start+"-"+c.end]  ||
                                           p[c.end+"-"+c.start]) &&
                                          (p[c.start+"-"+c.end] = true,
                                           p.result.push(c));
                                           return p;
                                        },{"result":[]});
console.log(reduced.result);

好吧，是的，我必须承认它看起来有点神秘，但它非常简单。

我们在这里使用带有初始值的 Array.prototype.reduce() 方法。这是我们的初始值{"result":[]}。当减少我们的 routeArr 数组时，我们开始的初始元素现在是一个具有单个属性命名结果和空数组值的对象。
reduce 提供了一个匿名回调函数，它有两个参数 (p,c) p 代表前一个，c 代表当前。所以在第一个运行 p 是我们的初始化对象，我的意思是这个 {"result":[]} 和 c 是数组索引 0 处的项目 (routeArr)我们呼吁减少。所以第一轮c就是{start: 1, end: 2}.
在每一轮开始时，我们检查我们的 p 对象是否包含一个属性，它代表两个顺序中的当前元素值。所以检查是这样的 !(p[c.start+"-"+c.end] || p[c.end+"-"+c.start]) ，在人类术语中意味着 "is it true that you don't have a string property like c.start-c.end or c.end-c.start".. 例如在第一轮检查就像 "is it true that you don't have a string property like "1-2" 或 "2-1"。如果它有 (false) 我们什么也不做，如果没有我们执行以下操作；
&& (p[c.start+"-"+c.end] = true, p.result.push(c)); return p;。好的，第一个 && 将括号中的两条指令与前一条指令的条件联系起来，以评估为真。在 a && b 指令中，如果 a 的计算结果为真，JS 引擎只会计算 b。所以你明白了。再次从人类的角度来看，这就是发生的事情。 "is it true that you don't have a string property like "1-2" 或 "2-1" 变为真，我们创建一个值为真的属性 "1-2"。所以在下一轮中，如果我们遇到 1-2 或 2- 1 我们什么都不做。然后我们将当前对象推送到同一对象 (p.result) 的结果属性以成为其所有副本或双胞胎的唯一代表。然后我们 return p 减少周期的健康延续。

希望清楚。

Answer 4

我把下面的函数写的干干净净

var routeArr = [{
  start: 1,
  end: 2
}, {
  start: 1,
  end: 3
}, {
  start: 1,
  end: 5
}, {
  start: 2,
  end: 1
}, {
  start: 3,
  end: 1
}, {
  start: 4,
  end: 1
}];

routeArr.IsDuplicate = function(obj) {
    var i = this.length;
    var count = 0 
    while (i--) {
        if ((this[i].start === obj.start && this[i].end === obj.end ) || (this[i].start === obj.end && this[i].end === obj.start) ) {
            count++;
        }
    }
    return count>1;
}

for(var i = routeArr.length-1; i--;){
    if (routeArr.IsDuplicate(routeArr[i])) routeArr.splice(i, 1);
}

Answer 5

您的嵌套循环方法是 'ugly'- 但这不是你的问题。

您的实施错误是由于您的两个 for 循环都假定数组结构不会随着您的改变而改变，这导致您跳过了数组中的某些项目。

'i' 和 'j' 是 'stupid' 递增器 - for 循环并没有告诉代码在每次迭代时转到数组中的下一个项目，而是告诉它去转到 (array[last_index_i_used+1] - 因此，当您拼接某些内容时，您正在查看的数组会发生变化，并且行中的下一项会被忽略。

我看到了很多花哨的数组方法和 ES6 的建议，但我从你的问题中假设你对 JS 还是有点陌生，并且可以花一些时间来构建基础知识（无意冒犯）。

尝试递归递减函数：

function uniquify(inputArray, ind){
    var checkStart = inputArray[ind].start, checkEnd =inputArray[ind].end
    for (var i=(ind-1);i > -1; --i){
        var thisStart = inputArray[i].start, thisEnd = inputArray[i].end
        if ((thisStart == checkStart || thisStart == checkEnd) && (thisEnd == checkStart || thisEnd == checkEnd)){

            inputArray.splice(i,1)
        }
    }

    --ind
    if (ind > -1){
        uniquify(inputArray,ind)
    }
}
uniquify(routeArr,routeArr.length -1);

与嵌套的 for 循环相比，我更喜欢它，因为您永远不会比需要更频繁地访问相同的值，无论数组的大小如何，它都能保持性能一致。

但您可能想问问自己，定义 'routeArr' 的任何东西是否正在以一种智能的方式做它正在做的事情 - 充其量，它看起来像是在浪费内存和 CPU 存储数据效率低下。

从 Javascript 数组中删除等效但唯一的对象

Removing equivalent but unique objects from a Javascript array

javascript

arrays

javascript-objects