寻找单身狗

题目描述

第一行是一个整数n（1￡n￡1000000），第二行是n个整数，每两个整数之间有一个空格，题目保证有且仅有两个不同的整数出现一次，其他的整数都是出现两次。输出两个整数，分别代表两个单身狗伪造的号码，中间有一个空格，并且较小号码的先输出。

样例输入

6 2 2 1 1 4 3

样例输出

3 4

代码实现

import java.util.HashSet; import java.util.Scanner; public class Main { public static void main(String[] args) { HashSet<Integer> set = new HashSet<Integer>(); Scanner sc = new Scanner(System.in); int n=sc.nextInt(); sc.nextLine(); for(int i=0;i<n;i++){ int k=sc.nextInt(); if(!set.add(k)){ set.remove(k); } } Object[] A=set.toArray(); int a=(int) A[0]; int b=(int) A[1]; if(a<b) System.out.print(a+" "+b); else System.out.print(b+" "+a); } }

以下代码正确，但是OJ上运行时间超限

import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class p1406 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n=sc.nextInt(); int []a=new int[n]; for(int i=0;i<n;i++){ a[i]=sc.nextInt(); } findOnlyNum(a); } //遍历两次取出没有找到的相同的数字 public static List findOnlyNum(int[] array){ List<Integer> list = new ArrayList<Integer>(); for(int i = 0 ;i<array.length;i++){ int j = 0; for(;j<=array.length;j++){ if(i==j){ continue; } if(j==array.length){ break; } if(array[i]==array[j]){ break; } } if(j==array.length){//到末尾仍然没找到相同的 list.add(array[i]); } } for(int i=0;i<list.size();i++){ System.out.print(list.get(i)+" "); } return list; } }