0

假设我有一个元素对列表，例如 (1, 2) (3, 4)，其中不存在重复项，并且对于一对 (p, q) p != q。如何使用简单的代码从这些元素中形成一个集合（我不打算使用像不相交集合和联合这样的数据结构，而是使用 java 库 API——除非代码可以以简单的方式编写）。示例： (1, 2) (2, 4) (5, 6) (4, 7) (3, 5) 应该输出： {1, 2, 4, 7} 和 {3, 5, 6}

    List<Set<Integer>> list = new ArrayList<>();
    for(String s : pairs){
        String[] values = s.split(" ");
        Integer val1 = Integer.parseInt(values[0]);
        Integer val2 = Integer.parseInt(values[1]);

        Set<Integer> pairSet = new HashSet<>();
        pairSet.add(val1);
        pairSet.add(val2);

        boolean exists = false;
        for(Set<Integer> set : list){
            if(set.contains(val1) || set.contains(val2)) {
                set.addAll(pairSet);
                exists = true;
                break;
            }
        }
        if(!exists)
            list.add(pairSet);
    }

这是一种不正确的幼稚方法。如果我得到一个序列 (1 2) (3 4) 和 (2 3)，则输出变为 {1, 2, 3} 和 {3, 4}。

发生这种情况是因为集合列表是这样创建的：{1, 2} 然后 {3, 4} 然后当对 (2 3) 出现时，它不会合并 2 个集合。

我可以编写一个代码来检查第一个值是否存在于任何集合中，比如 S1，然后对于另一个值相同，比如 S2，然后合并：

    //loop -> s1 = find val1
    //loop -> s2 = find val2
    if s1 != null and s2 != null //merge s1 and s2
    if(s1 == null && s2 != null) //add val1 and val2 to s2
    if(s1 != null && s2 == null) //add val1 and val2 to s1
    if(both null) create a new set of val1 and val2

太多的循环和条件。有更简单的解决方案吗？

4

3 回答 3

0

Revised version:

Here, I have made it using what you referred to as Naive approach:

public static List<Set<Integer>> answer(String[] pairs){

    List<Set<Integer>> list = new LinkedList<>();
    // For each pair, separate the numbers
    //Initialize with initial set
    Set<Integer> init = new HashSet<>();
    String[] splitted = pairs[0].split(" ");
    init.add(Integer.parseInt(splitted[0]));
    init.add(Integer.parseInt(splitted[1]));

    list.add(init);

    // To be used to maintain set record ahead
    List<Set<Integer>> setsRecord = new LinkedList<>();

    boolean found = false;
    Integer i1, i2;
    for(String s : pairs){
        i1 = Integer.parseInt((splitted = s.split(" "))[0]);
        i2 = i2 = Integer.parseInt(splitted[1]);
        for(Set<Integer> set : list){
            if(set.contains(i1) || set.contains(i2)){
                // If element has already been found in a set, create a common set
                if(setsRecord.size() >= 1){
                    setsRecord.get(0).addAll(set);
                    // And remove this set
                    list.remove(set);
                }
                else{
                    set.add(i1);
                    set.add(i2);
                    // Maintain a record of this set
                    setsRecord.add(set);
                }
                found = true;
            }
        }
        // Empty the temporary set record
        setsRecord.clear();

        if(!found){
            Set<Integer> newSet = new HashSet<Integer>();
            newSet.add(i1);
            newSet.add(i2);
            list.add(newSet);
        }
        found = false;
    }
    return list;
}

Demo.

于 2017-05-13T21:22:01.767 回答
0

我正在发布解决方案。如果有人可以使此代码更简单，那就太好了。TIA

        static void formSet(String[] pairs) {

    List<Set<Integer>> list = new ArrayList<>();
    for(String s : pairs){
        String[] values = s.split(" ");
        Integer val1 = Integer.parseInt(values[0]);
        Integer val2 = Integer.parseInt(values[1]);

        Set<Integer> pairSet = new HashSet<>();
        pairSet.add(val1);
        pairSet.add(val2);

        Set<Integer> val1_set = null, val2_set = null;
        for(Set<Integer> set : list){
            if(set.contains(val1)) {
                val1_set = set;
            }

            if(set.contains(val2)) {
                val2_set = set;
            }
        }
        if(val1_set == null && val2_set == null)
            list.add(pairSet);
        if(val1_set != null && val2_set == null)
            val1_set.addAll(pairSet);
        if(val1_set == null && val2_set != null)
            val2_set.addAll(pairSet);
        if(val1_set != null && val2_set != null){
            list.remove(val2_set);
            val1_set.addAll(val2_set);
        }
    }

    for(Set<Integer> set : list){
        System.out.println(set);
    }
}

这是 codereview 的链接： https ://codereview.stackexchange.com/questions/163301/forming-a-set-from-a-pair-of-numbers

于 2017-05-14T07:57:46.747 回答
-1

如果您将每一对视为对图形边缘的描述，那么一个简单的 DFS 就可以解决问题。

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution
{
  static int n = 1000000;
  static ArrayList< ArrayList<Integer> > adj = new ArrayList<ArrayList<Integer>>();
  static Boolean[] visited = new Boolean[n];

public static void main (String[] args) throws java.lang.Exception
{
    String input[] = {"1 2", "3 4", "2 3","5 6"};
    System.out.println(answer(input));
}

public static void dfs(int u,Set<Integer> res){
    visited[u] = true;
    for(int e : adj.get(u)){
        if(!visited[e])
             dfs(e,res);
    }
    res.add(u);
}
static void init(){
    for(int i = 0 ; i < n ; i++)
        adj.add(new ArrayList<Integer>());
}

public static List<Set<Integer>> answer(String[] pairs){
    init();
    List<Set<Integer>> list = new LinkedList<>();
    Set<Integer> elements = new HashSet<Integer>();
    for(int i = 0 ; i < pairs.length ; i++){
    String[] splitted = pairs[i].split(" ");
     int u = Integer.parseInt(splitted[0]);
     int v = Integer.parseInt(splitted[1]);
        adj.get(u).add(v);
        adj.get(v).add(u);
        visited[u] = visited[v] = false;
        elements.add(u);elements.add(v);
    }

    for(int e : elements){
        if(!visited[e]){
            Set<Integer> tmp = new HashSet<Integer>();
            dfs(e,tmp);
            list.add(tmp);
        }
    }
    return list;
}
}
于 2017-05-13T20:45:46.353 回答