只出现一次的数字III(给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。)
程序员文章站
2022-07-15 11:59:23
...
给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。
示例 :
输入: [1,2,1,3,2,5]
输出: [3,5]
做题思路:先将字符串自己异或一边,得到一个数。找到其二进制状态下为 1 的任一位置。两个只出现一次的元素在这个位置上的数字一个为 1 另一个为 0。那么我们可以把这个数组的的元素分为两部分,一部分在这一位的数字为 1 ,另一部分在这一位的数字为 0. 然后把这两部分的数字与自己异或,就会的到两个数。这两个数就是只出现一次的元素。
public class lianxi{
public static void main(String[] args){
Solution S = new Solution();
int[] nums = new int[] {1,2,1,3,2,5};
int[] a = S.singleNumber(nums);
for(int i = 0; i< 2 ;i++) {
System.out.print(a[i] + " ");
}
}
}
class Solution {
public int[] singleNumber(int[] nums) {
int a = nums[0];
int b = 0;
int c = 0;
int n = 1;
int[] result = new int[2];
for(int i = 1; i<nums.length;i++){
a ^=nums[i];
}
while(true){
if((a & n )== n ){
//找到为 1 的位置
break;
}
n *= 2;
}
for(int i = 0; i < nums.length; i++){
if((nums[i] & n )==n){
b ^= nums[i];
}else{
c ^=nums[i];
}
}
result[0] = b;
result[1] = c;
return result;
}
}