1

How can I reduce a Map<Integer, List<Integer>>?

Let a reduce'd map be a map for which each Integer value of List<Integer> is unique and not duplicated.

Example:

Map A: 

 0 --> (0)
 1 --> (1, 2) 
 2 --> (2, 1)

would reduce to:

 0 --> (0)
 1 --> (1, 2)

or 

 0 --> (0)
 2 --> (2, 1)

Notice that either deletion of key 1 or 2 is acceptable since it produces a reduced map.

EDIT: When an element maps to itself, it should remain separate, such as 0 --> 0. However, when multiple values have Integer's in common, they should be merged.

4

3 回答 3

1

尝试这个

class ReducedMap extends HashMap<Integer, List<Integer>> {
    private Set<Set<Integer>> set = new HashSet<Set<Integer>>();

    @Override
    public List<Integer> put(Integer key, List<Integer> value) {
        Set<Integer> set = new HashSet<Integer>(value);
        if (!this.set.add(set)) {
            return new ArrayList<Integer>(set);
        }
        return super.put(key, value);
    }
      ...
于 2013-04-18T04:21:50.910 回答
0

保留一个 ArrayList，我们称之为“合并”。

您应该使用 HashSet 来检测重复值。检查元素（列表中的值）是否在 HashSet 中，如果是则忽略它，否则将其放入 HashSet 并将其添加到“合并”ArrayList。

显然，您必须在此逻辑的开头添加一个案例，以不考虑元素是否映射到自身。

该算法将如下所示：

  1. 声明一个名为“ret”的 Map> 和一个名为“merged”的 ArrayList 和一个名为“duplicate_checker”的 HashSet

  2. 对于输入 Map 中的每个 List

    2.1 如果映射到自身，则放入“ret”

    2.2 否则，对于当前列表中的每个元素，如果它不在“duplicate_checker”中，则将其放在那里并将其添加到“合并”中

  3. 将“合并”改为“撤消”

  4. 返回“ret”

希望这可以帮助。

于 2013-04-18T04:49:07.777 回答
0

像这样的东西应该工作。

版本 #2，第一个有错误。

我会使用Pair类，因为我们将从地图中提取所有条目并将它们放在Pair的向量中。

private static class Pair {

    public Pair(Integer k, List<Integer> l) {

        this.k = k;
        this.s = new HashSet<Integer>();
        this.s.addAll(l);
    }

    public Integer k;
    public Set<Integer> s;
}

接下来，我们需要一个方法来检查两个集合是否有一些共同的元素。

public static boolean intersect(Set<Integer> a, Set<Integer> b) {

    Set<Integer> tmp = new HashSet<Integer>(a);
    tmp.retainAll(b);

    return !tmp.isEmpty();
}

reduce 方法接受一个映射并返回一个新的缩减映射。

public static Map<Integer, List<Integer>> reduce(Map<Integer, List<Integer>> m) {

首先，我们将地图转换为Pair数组；这将允许有效地迭代和消除键。

    int cnt = 0;
    Pair[] entries = new Pair[m.size()];

    for (Integer k : m.keySet()) {

        List<Integer> l = m.get(k);
        entries[cnt] = new Pair(k, l);
        ++cnt;
    }

然后我们针对任何其他条目测试每一对；如果它们有共同的元素，我们删除后者，但首先我们将其合并到前者中。

    for (int i = 0; i < m.size(); ++i) {

        for (int j = i + 1; j < m.size(); ++j) {

            if (entries[i] != null && entries[j] != null && intersect(entries[i].s, entries[j].s)) {

                Set<Integer> si = entries[i].s;
                Set<Integer> sj = entries[j].s;

                si.addAll(sj);
                entries[j] = null;
            }
        }
    }

最后，我们将数组转换回映射，跳过删除的元素。

    Map<Integer, List<Integer>> r = new HashMap<Integer, List<Integer>>();

    for (int i = 0; i < m.size(); ++i)
        if (entries[i] != null)
            r.put(entries[i].k, new ArrayList<Integer>(entries[i].s));

    return r;
}
于 2013-04-18T04:53:34.140 回答