欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

NowCoder 数组中只出现一次的数字 异或运算

程序员文章站 2022-07-15 12:13:21
...

题意:一个数组中有两个数字只出现了一次,其他都出现了两次,找出这两个数字
思路:用Map存储数字出现次数复杂度也不高,但是没有完全按照题意要求来做,正确的做法是用异或运算,将数组中所有数字异或起来,所有相同的数字会抵消,只剩下两个只出现一次的不同的数字,这时可以找到异或结果二进制中第一个1,把原数组划分成两个子数组,即在那位带1和不带1的,之后再次在两个数组异或求出两数

public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        int ans = array[0];
        for (int i = 1; i < array.length; i++)
            ans ^= array[i];
        int temp = ans, cnt = 0;
        while (temp%2 != 1) {
            temp >>= 1;
            cnt++;
        }
        int j = 0, k = 0;
        int[] t1 = new int[array.length];
        int[] t2 = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            if ((array[i]&((int)Math.pow(2, cnt))) != 0)
                t1[j++] = array[i];
            else
                t2[k++] = array[i];
        }
        num1[0] = t1[0]; num2[0] = t2[0];
        for (int i = 1; i < j; i++)
            num1[0] ^= t1[i];
        for (int i = 1; i < k; i++)
            num2[0] ^= t2[i];
        return;
    }
}
相关标签: 算法 数据结构