找出数组中唯一的数(三同一异)

题目

输入一组未排序的整数,其中一个数字只出现一次,剩下的所有数字都出现了三次。找出这个只出现一次的数字。例如输入: [1,2,2,2,3,3,3],输出为1

输入描述:

1
2
输入包含两行:
第一行有一个整数n(1 ≤ n ≤ 100000),表示数组数字个数n,个数满足题意。 第二行为n个整数,范围均在32位整数,以空格分隔,保证输入数据合法

输出描述:

1
出现一次的那个数字

示例1

输入

1
7 1 2 2 2 3 3 3

输出

1
1

思路

相同的数,将其由十进制转换成二进制,在相同的二进制位上是一样的。

现在假如有三个相同数,用sum数组来模拟它们的二进制表现形式,二进制表示为(11011),将它们用数组存储起来并在相同的位上相加,得到sum={3,3,0,3,3}。

到这一步就很清晰了,让每一位mod3即可将消除这三个相同的数对sum数组带来的影响。

最后sum数组里面存储的就是那个唯一的数的二进制表示了。将其转换成十进制即可。

这里也可以推广到n个相同的,一个唯一的数,找出那个唯一的数,同理。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Scanner;
public class Main {
static int[] sum = new int[32];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
int ans = 0;

for(int i = 0; i < t; i++) {
int val = sc.nextInt();
int index = 31;
while(val > 0) {
sum[index--] += val % 2;
val >>= 1;
}
}
for(int i = 0; i <= 31; i++) {
ans = ans * 2 + sum[i] % 3;
}
System.out.println(ans);
}
}
-------------本文结束感谢您的阅读-------------
0%