剑指 Offer 56 - I.数组中数字出现的次数

不在于那些特定时刻，而在于人生的时时刻刻，成为有勇气的人，不再犹豫彷徨。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* singleNumbers(int* nums, int numsSize, int* returnSize)
{
    int ret = 0;
    for(int i = 0;i>j)&1)
        {
            break;
        }
    }
    int x = 0,y = 0;
    for(int k = 0;k>j)&1)
        {
            x^=nums[k];
        }
        else
        {
            y^=nums[k];
        }
    }
    int*arr=(int*)malloc(sizeof(int)*2);
    arr[0]=x;
    arr[1]=y;
    *returnSize = 2;
    return arr;
}

第一步：

看到题目中有两个相同的数字，我们应该条件反射想到异或，因为两个相同数字异或就会消失。

所以我们定义一个ret=0来与数组中的每个数字进行异或，最终得到的结果即为那两个不同的数字（假设为x,y）异或的结果，即为ret == x^y.

int ret = 0;
for (int i = 0; i < numsSize; i++)
{
	ret ^= nums[i];
}

第二步：

怎样分别找出x和y呢？

这里就要进行找规律，毕竟是算法题嘛。

首先，清楚一个事情，那就是ret一定不是0，因为只有两个相同的数字异或才是0，x和y可是我们精心筛选出来的两个不相同的数字耶~

既然ret一定不为0，那么它就一定有为1的位，假设ret的第n位为1，那么说明x和y的第n位，一个为1，一个为0。

按照这个条件，我们将第n位为1的分成一组，第n位为0的分成一组，这样我们就把x和y分到了两组之中，每一组除了x或者y，剩下的就都是相同的数字对，异或就可以让它们一起消失q(≧▽≦q)

---

实现：

来看一下如何实现吧~

对于ret而言，我们从低位到高位找到它的一个为1的位，该如何寻找？

首先，我们知道二进制ret一共有32位，那么，该如何从低到高找到第一次出现1的位呢？其实，我们只需要让ret的每一位和1进行按位与。

又因为我们进行条件判断时，非0默认为真，因此可以将它作为判断条件放到if后面的括号里面

如何使得ret的每一位与1进行按位与？

有两种办法，一种是ret动，将ret一位一位的右移，这样就可以每一位都在最后一位和1进行按位与；还有一种是1动，将1一位一位的左移，这样就可以使得1和ret的每一位进行按位与。

但是这里有个问题，我们使用vs编译器运行这两种情况时，编译器都可以通过，但是在leetcode上面检查则更加严格，它是不允许1左移31位的，因为左移31位就到了符号位上去，因此在leetcode上提交时，我们选择 if((ret>>j) &1)这种方法。

int j = 0;//为了能够看到j在循环结束后是几而非局部变量
for (; j < 32; j++)//开始是个空语句，不执行什么东西
{
	if (ret & (1 << j))//if((ret>>j) &1)
	{
		break;
	}
}

接下来我们的任务就是将原数组分为两组，第j位为1的为a组，第j位为0的为b组，则x和y一定会分别进入a，b组。

a组和b组数据就变成了：其他数出现两次，只有一个数（x或y）出现一次，最终在两组中分别进行异或，就可以消掉两组中的相同数字，余下x和y。

如何实现分组与异或？

其实可以将这两个步骤合并为一步，遍历数组中的元素，接着，根据它的第j位是否为0进行分组，在每一组里直接进行异或

int x = 0, y = 0;
for (int k = 0; k < numsSize; k++)
{
	if ((nums[k]>>j) & 1)
	{
		x ^= nums[k];
	}
	else
	{
		y ^= nums[k];
	}
}

最终返回x和y这两个值，但因为我们不能返回两个值，因此我们把x和y放在数组中进行返回。

同时通过输出型参数来表示这个返回数组的大小，因此我们将地址returnSize解引用最终能够对实参进行修改。

int* arr = (int*)malloc(sizeof(int) * 2)

arr[0] = x;
arr[1] = y;

*returnSize = 2;

return arr;