找出数组中两个只出现一次的数字怎样实现?

KLQ 2020-04-15 15:39:36 java常见问答 8480

代码如何实现找出数组当中只出现一次的数字呢?具体的代码实现和思路是怎样的?下面一起来看看实例。

题目:

一个整型数组当中,除去2个数字以外,其它的数字都已经出现过了2次。

请写程序,将这2个只出现了一次数字找出来。

思路1:

可以使用位运算来实现。

假如将所有数字相异或,那么最后的结果肯定是那两个只出现一次的数字异或的结果,所以,依据异或的结果1所在的最低位,将数字分成2半,每一半里都还有只出现1次的数据和成对出现的数据,这样继续对每一半相异或那么就能够分别求出2个只出现了1次的数字了。

代码实现:

class Solution
{
    public:
        void FindNumsAppearOnce(vector < int > data, int * num1, int * num2)
        {
            if (data.size() < 2)
                return;
            int size = data.size();
            int temp = data[0];
            for (int i = 1; i < size; i++)
                temp = temp ^ data[i];
            if (temp == 0)
                return;
            int index = 0;
            while ((temp & 1) == 0)
            {
                temp = temp >> 1;
                ++index;
            }
            * num1 = * num2 = 0;
            for (int i = 0; i < size; i++)
            {
                if (IsBit(data[i], index))
                    *
                    num1 ^= data[i];
                else
                    *num2 ^= data[i];
            }
        }
    bool IsBit(int num, int index)
    {
        num = num >> index;
        return (num & 1);
    }
};

思路2:

首先:位运算中异或的性质:

2个相同数字异或=0,一个数和0异或还是它本身。

当只有一个数出现1次的时候,将数组中所有的数,依次异或运算,最后剩下的就是落单的数,因为成对儿出现的都抵消了。

按照这个思路:

看一看2个数(我们假设是AB)出现一次的数组。

首先还是先异或,剩下的数字肯定是A、B异或的结果,这个结果的二进制中的1,表现的是A和B的不同的位。

取第一个1所在的位数,假设是第3位,接着把原数组分成两组,分组标准是第3位是否为1。

如此,相同的数肯定在一个组,因为相同数字所有位都相同,而不同的数,肯定不在一组。

之后将这两个组按照最开始的思路,依次异或,剩余的2个结果就是这2个只出现1次的数字。

代码实现:

public class Solution
{
    public void FindNumsAppearOnce(int[] array, int[] num1, int[] num2)
    {
        int length = array.length;
        if (length == 2)
        {
            num1[0] = array[0];
            num2[0] = array[1];
            return;
        }
        int bitResult = 0;
        for (int i = 0; i < length; ++i)
        {
            bitResult ^= array[i];
        }
        int index = findFirst1(bitResult);
        for (int i = 0; i < length; ++i)
        {
            if (isBit1(array[i], index))
            {
                num1[0] ^= array[i];
            }
            else
            {
                num2[0] ^= array[i];
            }
        }
    }
    private int findFirst1(int bitResult)
    {
        int index = 0;
        while (((bitResult & 1) == 0) && index < 32)
        {
            bitResult >>= 1;
            index++;
        }
        return index;
    }
    private boolean isBit1(int target, int index)
    {
        return ((target >> index) & 1) == 1;
    }
}

思路3

代码实现:

/**
 * 数组中有两个出现一次的数字,其他数字都出现两次,找出这两个数字
 * @param array
 * @param num1
 * @param num2
 */
public static void findNumsAppearOnce(int[] array, int num1[], int num2[])
{
    if (array == null || array.length <= 1)
    {
        num1[0] = num2[0] = 0;
        return;
    }
    int len = array.length, index = 0, sum = 0;
    for (int i = 0; i < len; i++)
    {
        sum ^= array[i];
    }
    for (index = 0; index < 32; index++)
    {
        if ((sum & (1 << index)) != 0) break;
    }
    for (int i = 0; i < len; i++)
    {
        if ((array[i] & (1 << index)) != 0)
        {
            num2[0] ^= array[i];
        }
        else
        {
            num1[0] ^= array[i];
        }
    }
}
/**
 * 数组a中只有一个数出现一次,其他数都出现了2次,找出这个数字
 * @param a
 * @return
 */
public static int find1From2(int[] a)
{
    int len = a.length, res = 0;
    for (int i = 0; i < len; i++)
    {
        res = res ^ a[i];
    }
    return res;
}
/**
 * 数组a中只有一个数出现一次,其他数字都出现了3次,找出这个数字
 * @param a
 * @return
 */
public static int find1From3(int[] a)
{
    int[] bits = new int[32];
    int len = a.length;
    for (int i = 0; i < len; i++)
    {
        for (int j = 0; j < 32; j++)
        {
            bits[j] = bits[j] + ((a[i] >>> j) & 1);
        }
    }
    int res = 0;
    for (int i = 0; i < 32; i++)
    {
        if (bits[i] % 3 != 0)
        {
            res = res | (1 << i);
        }
    }
    return res;
}

这样的程序还是比较容易写的,大家都有自己的思路了吗?可以参考上面的实例去尝试着写一下。更多Java实例,请继续来本站了解吧。