题目内容

题目:一个数组中除了两个数字之外,其余数字均出现了两次,如{1, 2, 3, 4, 1, 2, 5, 5, 4, 7}.查找这两个只出现一次的数字,要求时间复杂度为o（n）,空间复杂度为o（1）.

解法

基础知识

与（&）:全1为1,有0则0.    0&0=0; 0&1=1;1&1=1;

或（|）:有1则1,全0则0.    0|0=0; 0|1=1; 1|1=1;

异或（^）:相同为0,不同为1. 1^1=0; 0^0=0; 0^1=1;

思路如下：

将数组里全部数据异或一遍,由于相同数字异或结果为0,则这样可以消除所有重复的数字,结果与两个单次数字异或后的结果相同
因为两者是不同的数字,结果一定有一位为1.这说明在该位上这两个单数一个为0一个为1.由此我们将数组分成两部分,一部分为该位为0,另一部分为1,再分别对两组异或最终得到的两个数值就是单次出现的两个数字

解题步奏

全组异或
异或结果取出第一位不为0的位数
将数组数据根据改位数是否为零分开异或,结果则为两个单次数字

代码如下

Talk is cheap, show you my code!

/**
 * Created by IDEA.
 * User: mc
 * Date: 19/2/13
 * Time: 上午9:19
 */
public class TowSingleNum
{
    public static void main(String[] args)
    {
        int[] num = {1, 2, 3, 4, 1, 2, 5, 5, 4, 7};
        execute(num);
    }

    /**
     * 获取异或结果
     *
     * @param num
     * @return
     */
    private static int getSum(int[] num)
    {
        int sum = 0;
        for (int item : num) {
            sum ^= item;
        }
        return sum;
    }

    /**
     * 执行入口
     *
     * @param num
     */
    public static void execute(int[] num)
    {
        int sum = getSum(num);
        int index = getIndex(sum);
        int num1 = 0, num2 = 0;
        for (int item : num) {
            if (judge(item, index)) {
                num1 ^= item;
            } else {
                num2 ^= item;
            }
        }
        System.out.printf("%d, %d", num1, num2);
    }

    /**
     * 划分数组
     *
     * @param num
     * @param index
     * @return
     */
    private static boolean judge(int num, int index)
    {
        return ((num >> index) & 1) == 0;
    }

    /**
     * 获取第一个不同的位数
     *
     * @param sum
     * @return
     */
    private static int getIndex(int sum)
    {
        int index = 0;
        while ((1 & sum) == 0) {
            sum = sum >> 1;
            index++;
        }
        return index;
    }
}