快捷的中山网站建设,酒店网站设计,国外办公室设计欣赏,北京公司可以在上海建网站吗考察点
异或运算#xff0c;与运算知识点
题目
分析 本题目要求数组中只出现一次的俩个数字#xff0c;并且要求O(1)时间复杂度和空间复杂度。试想一下如果只有一个数字出现一次#xff0c;那么针对全部元素做异或运算就可以了#xff0c;因为相同元素异或为0。现在有俩…考察点
异或运算与运算知识点
题目
分析 本题目要求数组中只出现一次的俩个数字并且要求O(1)时间复杂度和空间复杂度。试想一下如果只有一个数字出现一次那么针对全部元素做异或运算就可以了因为相同元素异或为0。现在有俩个数字出现了一次那么我们其实可以依据数字位的一些特性我们可以首先异或全部元素这个值肯定是这俩个只出现一次的数字的异或值既然值不相同那么肯定从右起有一位元素是1这是这俩个数字不相同的原因之一我们可以再找出来到底是第几位元素然后再次遍历数组针对所有元素判断该位是否是1分别做异或运算即可
public class Forty{public static void main(String[] args) {int[] arr {2,4,3,6,3,2,5,5};getDifferentNum(arr);}public static void getDifferentNum(int[] arr) {int num 0;for (int i 0;iarr.length;i) {num num ^ arr[i];}//找到右起第一位不是0的int cnt 0;int oneNum 1;while(oneNum 0) {if((num oneNum) 0) {cnt;} else {break;}oneNum oneNum 1;}int numA 0;int numB 0;for(int i 0;iarr.length;i) {oneNum 1;if(((oneNum cnt) arr[i]) 0) {numA numA ^ arr[i];} else {numB numB ^ arr[i];}}System.out.println(numA);System.out.println(numB);}
}
