题目
把 这 个数放到一个长度为 的整数数组中,其中只有一个数出现了两次,找出这个数。
输入格式
第一行包含一个整数 ,表示数组的长度。
接下来一行给出 个用空格分隔的整数表示数组中的元素。
输出格式
输出出现了两次的那个数。
输入样例:
5
1 2 3 4 3
输出样例:
3
解题
方法一:哈希表
思路
使用哈希表给数组中每个数计数,返回出现了两次的数。
代码
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
int[] nums = new int[n];
for (int i = 0; i < n; ++i) {
in.nextToken();
nums[i] = (int) in.nval;
}
// 输入完成
int[] cnts = new int[n];
for (int num : nums) {
if (++cnts[num] == 2) {
System.out.println(num);
return;
}
}
}
}
方法二:数学
思路
若数组的长度为 ,那其中的数就是 ,把数组中的数加起来减去 即是出现两次的数。
使用这种方法需要注意数字太多时可能会溢出。
代码
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
int[] nums = new int[n];
for (int i = 0; i < n; ++i) {
in.nextToken();
nums[i] = (int) in.nval;
}
// 输入完成
int sum = 0;
for (int num : nums) sum += num;
int tmp = (n - 1) * n / 2;
System.out.println(sum - tmp);
}
}
方法三:位运算
思路
由异或运算的性质:对于任何数 ,都有 ,,那么我们只需要利用这一条把出现一次的数字全部消除即可。
具体来说:把 全部异或在一起得到一个数,再把它与数组中的所有数字都做一次异或运算,此时 中只出现一次的数字参与了两次异或运算被全部消除了,而出现两次的数字一共参与了三次异或运算,而我们知道 ,于是该数字就被保留了下来。
代码
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
int[] nums = new int[n];
for (int i = 0; i < n; ++i) {
in.nextToken();
nums[i] = (int) in.nval;
}
// 输入完成
int ans = 0;
for (int i = 1; i < n; ++i) ans ^= i;
for (int num : nums) ans ^= num;
System.out.println(ans);
}
}
评论区