思路:输入的每组数字用ArrayList<Integer> arr 存储,每个朋友圈(集合)用一个HashSet<Integer> tmp 表示,ArrayList<Integer> ls 用来存储找到的朋友圈。
先将最后一组数字(2个)作为HashSet<Integer> tmp的初始元素,然后依次判断它前面的每组数字是否出现在集合中,如果是则将这组数字加入集合,同时在 ArrayList<Integer> arr 中删除这组数字;否则跳过。
从后往前遍历 ArrayList<Integer> arr 的原因是该列表中的元素可能会减少。for循环中,下标 i-1 为偶数,表示它是每组数字的第一个;下标 i 为奇数,表示它是每组数字的第二个。
如果在遍历的过程中,集合中的元素个数发生了变化,则需要重新遍历一遍(思考为何?)。当某次遍历后集合中的元素个数没有发生变化,说明这个朋友圈已经找到。
对ArrayList<Integer> arr 剩余的几组数字采用相同的方法,直到arr.size()=0。
Java实现如下:
import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n = input.nextInt(); // 用来记录朋友圈的元素 List<HashSet<Integer>> ls = new ArrayList<HashSet<Integer>>(); // 用来记录未被处理的元素 ArrayList<Integer> arr = new ArrayList<Integer>(); for (int i = 0; i < 2 * n; i++) { arr.add(input.nextInt()); } while (arr.size() > 0) { // 用来保存朋友圈的元素,初始化为arr的最后2个元素 HashSet<Integer> tmp = new HashSet<Integer>(); tmp.add(arr.remove(arr.size() - 1)); tmp.add(arr.remove(arr.size() - 1)); while (true) { // 记录遍历前的tmp大小 int k = tmp.size(); // 从后往前遍历一次 for (int i = arr.size() - 1; i > 0; i = i - 2) { // 如果每组数字中有任意一个出现在tmp中,将2个数字都add if (tmp.contains(arr.get(i)) || tmp.contains(arr.get(i - 1))) { tmp.add(arr.remove(i)); tmp.add(arr.remove(i - 1)); } } // 如果遍历完一次以后,tmp大小没有变 if (k == tmp.size()) { break; } } // 得到一个朋友圈 ls.add(tmp); } // 打印朋友圈和人数 for (int i = ls.size() - 1; i >= 0; i--) { System.out.println(ls.get(i)); System.out.println(ls.get(i).size()); } } }
运行结果:
输入: 8 1 2 2 3 5 4 3 4 6 7 8 6 9 10 10 11 输出: [1, 2, 3, 4, 5] 5 [6, 7, 8] 3 [9, 10, 11] 3