小米java笔试题 朋友圈

Question

假如n=5，m=3，r={{1,2}，{2,3}，{4,5}}，表示一共5个人，1和2是朋友，2和3是朋友1和3通过2间接是朋友。那么1,2,3属于一个朋友圈，4,5属于一个朋友圈一共两个朋友圈。
下面是我写的代码  但是感觉不是最优答案 请大牛们给出最优答案
谢谢各位
package me.luger.xiaomi;import java.util.LinkedList;
import java.util.List;public class Friends {
 /**
     *@site:www.luger.me
     * 根据二维数组输出朋友圈
     * @param r 关系数组
     * @return void
     * */
    public static void main(String[] args) {
        int[][] r = { { 1, 5 }, { 3, 5 }, { 4, 5 }, { 1, 4 }, { 5, 6 },
                { 8, 1 }, { 9, 20 }, { 98, 11 }, { 13, 76 }, { 98, 77 },{2,1} };
        friends( r);
    }    /**
     * 根据二维数组输出朋友圈
     * @param r 关系数组
     * @return void
     * */
    static void friends(int[][] r) {
        boolean[] b = new boolean[r.length];//标志是否遍历过并加入朋友圈集合中
        int s = r[0][0];//从此处开始遍历
        int temp = 0;
        List<Integer> list = new LinkedList<Integer>();//插入操作多所以使用LinkedList
        boolean flag = true;//判断循环条件是否终止        b[0] = true;//从第一个开始，就代表已经遍历加入集合所以设置为true
        while (true && flag) {
            list = new LinkedList<Integer>();
            list.add(s);
            for (int j = 0; j < list.size(); j++) {
                int key = list.get(j);
                for (int i = 0; i < r.length; i++) {
                    if (r[i][0] == key) {
                        if (!list.contains(r[i][1])) {
                            list.add(r[i][1]);
                        }
                        b[i] = true;
                    } else if (r[i][1] == key) {
                        if (!list.contains(r[i][0])) {
                            list.add(r[i][0]);
                        }
                        b[i] = true;
                    }
                }
            }            System.out.println(list);            for (int i = 0; i < b.length; i++) {
                if (b[i] == false) {
                    s = r[i][0];
                    break;//结束for循环继续while循环
                }else if (i == b.length - 1&&allScan(b))//使用短路与，减少复杂度
                    flag = false;
            }        }
    }    /**
     * 判断一个boolean数组里面的值是不是全为true
     * @param b 接受的数组
     * @return boolean 如果数组全为true返回true
     * */
    static boolean allScan(boolean[] b){
        for(int i=0;i<b.length;i++){
            if(b[i] == false){
                return false;
            }
        }
        return true;
    }}

Answer 1

只会这种中规中矩的做法public class Test {
public static void main(String[] args) throws Exception {
int[][] r = { { 1, 5 }, { 3, 5 }, { 4, 5 }, { 1, 4 }, { 5, 6 },
{ 8, 1 }, { 9, 20 }, { 98, 11 }, { 13, 76 }, { 98, 77 },
{ 2, 1 } };
Set<FriendSquare> squareSet = calculateFriendSquare(r);
for(FriendSquare square : squareSet){
System.out.println(square.toString());
}
}

private static Set<FriendSquare> calculateFriendSquare(int[][] array){
//每个人对应的朋友圈
Map<Integer, FriendSquare> squareMap = new HashMap<Integer, FriendSquare>();
for(int[] arr : array){
//此次分析所关联的朋友圈
List<FriendSquare> squareList = new ArrayList<FriendSquare>();
for(int id : arr){
FriendSquare square = squareMap.get(id);
//如果当前没有已经存在的朋友圈，新建一个
if(square == null){
square = new FriendSquare();
square.addFriend(id);
squareMap.put(id, square);
}
squareList.add(square);
}
//合并此次相关的朋友圈，并刷新map
FriendSquare square = squareList.get(0);
for(int i = 1 ; i < squareList.size(); i ++){
if(square != squareList.get(i)){
square.merge(squareList.get(i));
for(int id : squareList.get(i).getFriendIds())
squareMap.put(id, square);
}
}
}
Iterator<FriendSquare> iterator = squareMap.values().iterator();
Set<FriendSquare> resultSet = new HashSet<FriendSquare>();
while(iterator.hasNext()){
FriendSquare square = iterator.next();
if(!resultSet.contains(square))
resultSet.add(square);
}
return resultSet;
}
}class FriendSquare {
private Set<Integer> friendSet = new HashSet<Integer>(); public boolean isContains(int id) {
return friendSet.contains(id);
}

public Integer[] getFriendIds(){
return friendSet.toArray(new Integer[friendSet.size()]);
} public void merge(FriendSquare square) {
Iterator<Integer> iterator = square.friendSet.iterator();
while(iterator.hasNext())
addFriend(iterator.next());
}

public void addFriend(int id){
friendSet.add(id);
}

public String toString(){
StringBuffer sb = new StringBuffer();
for(Integer id : friendSet)
sb.append(id + ",");
return sb.toString();
}
}