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 three times except
12  *         for 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 public class SingleNumber2 {
18 
19     /**
20      * @param args
21      */
22     public static void main(String[] args) {
23         int[] A1 = { 1 };
24         int[] A2 = { 1, 2, 3, 4, 1, 2, 3, 1, 2, 3 };
25         int[] A3 = { 1, 1, 2, 4, 2, 4, 3, 5, 3, 1, 2, 3, 4 };
26         int[] A4 = { 1, 1 };
27         int[] A5 = { 1, 1, 1, 2, 2, 2, 3, 3 };
28         System.out.println(singleNumber(A1));
29         System.out.println(singleNumber(A2));
30         System.out.println(singleNumber(A3));
31         System.out.println(singleNumber(A4));
32         System.out.println(singleNumber(A5));
33     }
34 
35     /**
36      * 
37      * @param A
38      * @return
39      */
40     public static int singleNumber(int[] A) {
41         Arrays.sort(A);
42         int ret = 0;
43         for (int i = 0; i < A.length; i = i + 3) {
44             if (i == A.length - 1 || i == A.length - 2) {
45                 ret = A[i];
46                 break;
47             } else if (!(A[i] == A[i + 1] && A[i] == A[i + 2])) {
48                 ret = A[i];
49                 break;
50             }
51         }
52         return ret;
53     }
54 
55 }