网站开发+职位描述,saas 平台架构做网站,响应式网站wordpress摄影,建站总结报告1 问题
一个整型数组里除了两个数字之外#xff0c;其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 2 分析
第一种方法#xff1a;我们用位运算
我们想到位运算
#xff08;1#xff09; a^a0#xff08;2#xff09;a^0a#xff08;2#xff09;a…1 问题
一个整型数组里除了两个数字之外其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 2 分析
第一种方法我们用位运算
我们想到位运算
1 a^a02a^0a2a^b^ca^(b^c)(a^c)^b 1) 对所有运算进行异或运算最后结果就是两个出现一次的元素异或结果接下来问题演变成了我们知道两个不同数据的异或值那么怎么求出这两个值呢
2) 因为这两个元素不相等所以异或的结果肯定不是0也就是可以再异或的结果中找到1位不为0的位例如异或结果的最后一位为1我们把这个位置标记为index,然后我们把原始数组分为2个数组第一个数组中的每个数组的第index位都是1的数组和每个数组的第index位都是0的数组然后我们再把这个两组数据进行异或处理分别求出的数据就是我们不同的两个数。 第二种方法我们用map,key为元素值如果出现几次放进value里面去然后最后遍历如果value是1的话我们得到2个key就行。 3 代码实现
用异或处理的C版本如下
#include iostream
#include vectorusing namespace std;void findApperanceTwoNumber(vectorint input, int num1, int num2)
{if (input.size() 2){std::cout input.size() 2 std::endl; return;}int sum 0;//对所有数据进行异或处理for (int i 0; i input.size(); i){sum ^ input[i];}//我们通过index找到这个2个不同元素异或值的位1的位置int index 0;for (int i 0; i 32; i){if (((sum i) 1) 1){index i;break;}}//然后我们遍历数组把每个数据的第index位和1进行异或处理分别得到结果为1和0的2组数据然后把这2组数据分别异或处理的和就是2个不同的数据for (int i 0; i input.size(); i){if (((input[i] index) 1) 1){num1 ^ input[i];}else{num2 ^ input[i];}}
}int main()
{vectorint v2;v2.push_back(2);v2.push_back(2);v2.push_back(3);v2.push_back(4);v2.push_back(6);v2.push_back(6); int a 0, b 0;findApperanceTwoNumber(v2, a, b);std::cout a is a b is b std::endl; return 0;
}
用map处理的C版本如下
#include iostream
#include vector
#include mapusing namespace std;void findApperanceTwoNumber2(vectorint input, int num1, int num2)
{if (input.size() 2){std::cout input.size() 2 std::endl;return;}mapint, int datas;for (int i 0; i input.size(); i){//C里面map如果要通过key获取value的话我们先需要探测map里面是不是有这个key我们可以count函数,这里如果是java版本的话就算key不存在的话我们执行get方法操作得到的null,没关系。if (datas.count(input[i])){if (datas[input[i]] 1){//这里用数组形式是因为如果用insert如果发现key一样的话再次插入会失败我们所以用数组的形式这里是通过key更新valuedatas[input[i]] 2;}}else{ datas[input[i]] 1;}}///然后我们再遍历mapfor (mapint, int::iterator it datas.begin(); it ! datas.end(); it){if (it-second 1){if (num1 0){//这里是获取keynum1 it-first;}else{//这里是获取valuenum2 it-first;}}}
}int main()
{vectorint v2;v2.push_back(2);v2.push_back(2);v2.push_back(3);v2.push_back(4);v2.push_back(6);v2.push_back(6); int a 0, b 0;findApperanceTwoNumber2(v2, a, b);std::cout a is a b is b std::endl; return 0;
}
运行结果如下
a is 3 b is 4 用map处理的java版本如下
import java.io.*;
import java.util.ArrayList;
import java.util.*;class St
{public St() {}ArrayListInteger findApperanceTwoNumber2(int[] datas) {ArrayListInteger list new ArrayListInteger();if (datas null || datas.length 2)return list; HashMapInteger, Integer map new HashMapInteger, Integer();for (int i 0; i datas.length; i) {if (map.containsKey(datas[i])) {if (map.get(datas[i]) 1){map.put(datas[i], 2);}} else {map.put(datas[i], 1);}}SetInteger keys map.keySet();for (int key : keys) {if (map.get(key) 1) {list.add(key);}}return list;}
}class test
{public static void main (String[] args) throws java.lang.Exception{ArrayListInteger list new ArrayListInteger();St s new St();int [] a {1, 1, 3, 5, 4, 4};list s.findApperanceTwoNumber2(a);for (int i : list){System.out.println(value is i);}}
}
运行结果如下
value is 3
value is 54 总结
如果我们有2个不同数的异或值那我们怎么知道这2个数据值呢这里不是说直接知道这2个元素的数组意思不然还要你求干吊 因为这两个元素不相等所以异或的结果肯定不是0也就是可以再异或的结果中找到1位不为0的位例如异或结果的最后一位为1我们把这个位置标记为index,然后我们把原始数组分为2个数组第一个数组中的每个数组的第index位都是1的数组和每个数组的第index位都是0的数组然后我们再把这个两组数据进行异或处理分别求出的数据就是我们不同的两个数。
C版本的map操作我们最好是用数组形式因为数组形式既可以赋值和可以用来进行修改操作如果是用insert函数插入的当key是同样而value不是同样值的时候会失败然后我们获取的话最好也是通过数组形式的key获取但是获取之前我们需要判断key是否存在map里面的key没有如果没在的话直接获取就有问题但是java的话就算没有key,获取的也是null值没关系。
C的话我们map用count(key)函数来判断是否key存在而java的话我么可以用map的containsKey(key)函数判断key是否存在无论在C版本还是java版本我们要对map通过key获取value操作如果不是通过keySet来获取就是这个key必然存在map里面的时候我们都要先用上面的函数进行探测是否包含key,这样代码的健壮性好点。
