题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
解法1
利用HashMap来做这道题，时间复杂度为O(N)，空间复杂度为O(N)
代码
package nowcoder;
import java.util.HashMap;
import java.util.Map;
/**
* @author god-jiang
* @date 2020/1/28 16:39
*/
//一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class FindNumsAppearOnce {
//HashMap解法
public static void findNumsAppearOnce(int[] array, int num1[], int num2[]) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < array.length; i++) {
if (map.containsKey(array[i])) {
map.put(array[i], 2);
} else {
map.put(array[i], 1);
}
}
//标识这两个数的顺序
int count = 0;
for (int i = 0; i < array.length; i++) {
if (map.get(array[i]) == 1) {
if (count == 0) {
num1[0] = array[i];
count++;
} else {
num2[0] = array[i];
}
}
}
}
}
解法2（重点）
利用位运算中的异或运算来解这道题。异或的性质就是两个相同的数字异或为0，一个数和0异或还是它本身。要是对位运算不熟悉的话可以先看这一篇文章：
god-jiang：神级运算——位运算zhuanlan.zhihu.com
用位运算可以达到时间复杂度为O(N)，空间复杂度为O(1)
思路
如果一个数组只有A和B是出现一次的数，我们把所有的数都异或了之后的结果就是A和B异或的结果。因为相同的数异或都等于0。异或的结果的二进制中至少会出现一个1，因为A和B不同，异或至少会出现一个1，我们取第一个1的位置，假设这个位置是第3位，我们把第3位为0的分成一组，把第3位为1的分成一组，各自异或，最后的结果就是出现一次的数。
代码
package nowcoder;
import java.util.HashMap;
import java.util.Map;
/**
* @author god-jiang
* @date 2020/1/28 17:32
*/
//一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class FindNumsAppearOnce {
//异或解法
public static void findNumsAppearOnce1(int[] array, int num1[], int num2[]) {
int temp = 0;
//异或的结果就是A和B的异或结果
for (int i = 0; i < array.length; i++) {
temp = temp ^ array[i];
}
int index = 1;
//找到异或结果第一位为1的位置为index
while ((index & temp) == 0) {
index = index << 1;
}
int result1 = 0;
int result2 = 0;
for (int i = 0; i < array.length; i++) {
if ((index & array[i]) == 0) {
result1 = result1 ^ array[i];
} else {
result2 = result2 ^ array[i];
}
}
num1[0] = result1;
num2[0] = result2;
}
}结果
总结
这道题目在牛客网上还是比较经典的一道题目，可以看出你对HashMap熟不熟悉，也可以看出你对位运算的理解程度。
今天的文章数组 出现次数_统计一个字符串的个数「建议收藏」分享到此就结束了，感谢您的阅读。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/87431.html
