思路:输入的每组数字用ArrayList<Integer> arr 存储,每个朋友圈(集合)用一个HashSet<Integer> tmp 表示,ArrayList<Integer> res 用来存储每个朋友圈的人数。
对于arr[i],i为偶数表示它是每组的第一个数字,i为奇数表示它是每组的第二个数字。
先将最后一组数字(2个)作为HashSet<Integer> tmp的初始元素,然后依次判断它前面的每组数字是否出现在集合中,如果是则将这组数字加入集合,同时在ArrayList arr 中删除这组数字;否则跳过。
如果在遍历的过程中,集合中的元素个数发生了变化,则需要重新遍历一遍。当某次遍历后集合中的元素没有发生变化,说明这个朋友圈已经找到。
对ArrayList<Integer> arr 剩余的几组数字采用相同的方法,直到arr.size()=0。
Java实现如下:
import java.util.ArrayList; import java.util.Collections; 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>(); ArrayList<Integer> res = new ArrayList<Integer>(); for (int i = 0; i < 2 * n; i++) { arr.add(input.nextInt()); } while (arr.size() > 0) { HashSet<Integer> tmp = new HashSet<Integer>(); tmp.add(arr.remove(arr.size() - 1)); tmp.add(arr.remove(arr.size() - 1)); int k = 2; while (k <= tmp.size()) { for (int i = arr.size() - 1; i >= 0; i--) { if (i % 2 == 1 && tmp.contains(arr.get(i))) { arr.remove(i); tmp.add(arr.remove(i - 1)); i = i - 2; } if (i % 2 == 0 && tmp.contains(arr.get(i))) { arr.remove(i); tmp.add(arr.remove(i)); i = i - 2; } } k++; } //ls.add(tmp); res.add(tmp.size()); } //for (HashSet<Integer> i : ls) { //System.out.println(i); //} Collections.sort(res, Collections.reverseOrder()); for (int i = 0; i < res.size(); i++) System.out.println(res.get(i)); } }
原文:http://www.cnblogs.com/zengzhihua/p/4805663.html