1 /**
 2  * 
 3  */
 4 package solution;
 5 
 6 import java.util.Arrays;
 7 
 8 /**
 9  * @author whh
10  * 
11  *         Given an array of integers, every element appears twice except for
12  *         one. Find that single one.
13  * 
14  *         Note: Your algorithm should have a linear runtime complexity. Could
15  *         you implement it without using extra memory?
16  * 
17  */
18 public class SingleNumber {
19 
20     /**
21      * @param args
22      */
23     public static void main(String[] args) {
24         int[] A1 = { 1 };
25         int[] A2 = { 1,2,3,4,1,2,3 };
26         int[] A3 = { 1,1,2,4,2,4,3,5,3 };
27         System.out.println(singleNumber(A1));
28         System.out.println(singleNumber(A2));
29         System.out.println(singleNumber(A3));
30     }
31 
32     /**
33      * @param A
34      * @return
35      */
36     public static int singleNumber(int[] A) {
37         Arrays.sort(A);
38         int ret = 0;
39         for (int i = 0; i < A.length; i = i + 2) {
40             if (i == A.length - 1) {
41                 ret = A[i];
42                 break;
43             } else if (A[i] != A[i + 1]) {
44                 ret = A[i];
45                 break;
46             }
47         }
48         return ret;
49     }
50 }