数组中只出现一次的两个数字

  • 时间:
  • 浏览:
  • 来源:互联网

数组中只出现一次的两个数字

题目描述

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

示例1

输入

[1,4,1,6]

返回值

[4,6]

说明

返回的结果中较小的数排在前面  

思路

相关知识点:

  • 逻辑运算的是补码
  • 正整数:补码=反码=原码
  • 负整数:反码=原码除符号位全部取反;补码=反码+1;
  • 异或(^) number ^ number = 0 ;number ^ 0 = number

一个整型数组里除了个数字之外,其他的数字都出现了两次,则所有数字异或的结果就是那个仅出现一次的数字。

 (n1 ^ n1) ^ (n2 ^ n2) ^ (n3 ^ n3) ^ …… ^ (nm ^ nm) ^ number
 = 0 ^ 0  ^ …… ^ number
 = number

本题中,有两个数字只出现一次,且根据上述可得所有数字异或的结果为 res = number1 ^ number2,而两位数不同,故res一定非0,在其二进制表示中一定有某一位为1

异或的二进制运算规则:
1 ^ 1 = 0 
1 ^ 0 = 1 
0 ^ 1 = 1 
0 ^ 0 = 0 

故在number1number2中,在该位置有某一位为1另一位为0

eg:
number1=100010
number2=101000
100010 ^ 101000 = 001010

可根据这一位是否为1,将数组分为两部分,则两部分的所有数字分别做异或,得到的两个结果就是要求的两个结果。

找到res中从左往右的第一个1的方法
方法1:

res &= -res
  • 逻辑运算的是补码

如果逻辑运算的是反码,则 res & -res = 0,负数的补码=反码+1,故能找到res中从左往右的第一个1。
eg:

res = 12
符号位 
    0      0 0 0 0 0 0 0 1 1 0 0   补码
    
-res = -12
符号位 
    1      0 0 0 0 0 0 0 1 1 0 0   原码
    1      1 1 1 1 1 1 1 0 0 1 1   反码
    1      1 1 1 1 1 1 1 0 1 0 0   补码
    
    res & -res =  0     0 0 0 0 0 0 0 0 1 0 0 

方法2:

	int temp=1;
    while ((res&temp)==0){
         temp=temp<<1;
    }
res = 12
符号位 
    0      0 0 0 0 0 0 0 1 1 0 0   补码
   
     res & temp
    1100 & 0001= 0;
    1100 & 0010= 0;
    1100 & 0100= 100;
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindNumsAppearOnce (int[] array) {
        // write code here
        int res = 0;
        for(int a:array) res ^= a;
        int[] nums = new int[]{0,0};
        res &= -res;
        for(int a:array){
            if( (a&res)==0 ) nums[0] ^= a;
            else nums[1] ^= a;
        }
        if(nums[0]>nums[1]){
            int temp = nums[0];
            nums[0] = nums[1];
            nums[1] = temp;
        }
        return nums;
    }
}

本文链接http://www.dzjqx.cn/news/show-617207.html