删除包含公共元素的子数组 [英] Remove sub-array contains common elements

问题描述

作为标题，如果输入为[[1,2,3]，[3,4]，[1,3]，[5,6]，[6,5]]，则输出应为[[1， 2,3,4]，[5,6]。
递归部分是错误的。在我的代码中，运行它后，我会得到[[1,2,3]，[1,3,4]，[5,6]]，这意味着我需要再次合并，但是我很困惑如何继续执行代码，直到没有子数组包含公共元素。

As the title, if the input is [[1,2], [3,4], [1,3], [5,6], [6,5]], output should be [[1,2,3,4], [5,6]]. It's wrong on the recursive part. In my code, after running it, I will get [[1,2,3],[1,3,4],[5,6]], which means I need once more merge, but I'm confused how to continue the code until no sub-array contains common element.

这是我的代码

function need_merge_or_not(arr)
{
  for (var i = 0; i <= arr.length-1; i++) {
      for (var j = i+1; j <= arr.length-1; j++) {
        var arr_new = arr[i].concat(arr[j]);
        //remove deplicates
        var arr_merge = arr_new.filter(function (item, pos) {return arr_new.indexOf(item) == pos});
        if (arr_merge.length < arr_new.length) {
          return true;
        }
      }
  }
  return false;
}


function merge(arr)
{
  if (arr.length >= 2) {
    for (var i = 0; i <= arr.length-1; i++) {
      for (var j = i+1; j <= arr.length-1; j++) {
        var arr_new = arr[i].concat(arr[j]);
        var arr_merge = arr_new.filter(function (item, pos) {return arr_new.indexOf(item) == pos});
        if (arr_merge.length < arr_new.length) {
          arr.splice(arr.indexOf(arr[i]), 1);
          arr.splice(arr.indexOf(arr[j]),1);
          arr.push(arr_merge);
        }
      }
        if (need_merge_or_not(arr)) {
          return merge(arr);
        }
    }
  }
  return arr;
}

推荐答案

您可以使用两个哈希表，一个用于项目及其组，然后用于结果 sets 。

You could use two hash tables, one for the items and their groups and on for the result sets.

基本上，该算法为同一组对象生成具有属性和数组的对象，因为它允许在分配新数组时保留对象引用。

Basically the algorithm generates for the same group an object with a property and an array, because it allowes to keep the object reference while assigning a new array.

主要部分是先对外部数组进行迭代，然后对内部数组进行迭代并检查内部，如果它是第一项，则检查哈希表是否存在，如果不存在，则生成带有values属性和空数组的新对象作为价值。还将实际对象分配给以项目为键的 sets 。

The main part is iterating the outer array and then the inner arrays and check inside, if it is the first item, then check the hash table for existence and if not exists, generate a new object with a values property and an empty array as value. Also assign the actual object to sets with item as key.

在下一步中，检查哈希表再次，如果不存在，则分配第一个元素的对象。

In a next step, the hash table is checked again and if not exist, then assign the object of the first element.

仅保留唯一值，将进行检查；如果该项目不存在，则检查该项目

To maintain only unique values, a check is made and if the item does not exist, the item is pushed to the hash table's values array.

然后通过检查第一个项目的对象是否不等于实际项目的对象，来连接数组的一部分。如果是这样，它将从 sets 集合中删除实际项目值中第一个项目的键，并将实际项目的数组与第一个项目对象的值合并。然后将值对象分配给实际项目的对象。

Then a part to join arrays follows by checking if the object of the first item is not equal to object of the actual item. If so, it delete from sets the key from the actual items's values first item and concat the array of the actual items to the first item's object's values. Then the values object is assigned to the actual item's object.

稍后，将集合映射到结果集，如下所示：迭代 sets 对象，然后将values属性作为值。

Later the sets are maped to the result set with iterating the sets object and the values property is taken as value.

var array = [[1, 2], [3, 4], [1, 3], [5, 6], [6, 5]],
    groups = {},
    sets = {},
    result;
    
array.forEach(function (a) {
    a.forEach(function (b, i, bb) {
        if (i === 0 && !groups[b]) {
            groups[b] = { values: [] };
            sets[b] = groups[b];
        }
        if (!groups[b]) {
            groups[b] = groups[bb[0]];
        }
        if (groups[b].values.indexOf(b) === -1) {
            groups[b].values.push(b);
        }
        if (groups[bb[0]] !== groups[b]) {
            delete sets[groups[b].values[0]];
            groups[bb[0]].values = groups[bb[0]].values.concat(groups[b].values);
            groups[b].values = groups[bb[0]].values;                    
        }
    });    
});

result = Object.keys(sets).map(function (k) {
    return sets[k].values;
});

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

这篇关于删除包含公共元素的子数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！