TOP101题解 | BM52#数组中只出现一次的两个数字#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @author Senky
 * @date 2023.08.26
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * @brief 首先对所有的数字进行异或运算，得到的结果是两个只出现一次的数字的异或结果（假设为X）。
 *      在X中找到任意一个为1的位，然后根据这个位将原数组分为两部分，分别进行异或运算。
 *      最终得到的两个结果就是两个只出现一次的数字。
 * @param nums int整型一维数组 
 * @param numsLen int nums数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
void sort(int* a,int* b)
{
    int temp = *a;
    if(*a > *b)
    {
        *a = *b;
        *b = temp;
    }
}

int* FindNumsAppearOnce(int* nums, int numsLen, int* returnSize ) 
{
    // write code here
    int XORResult = 0;
    for(int i = 0; i < numsLen; i++)
    {
        XORResult ^= nums[i];/*两个只出现一次的数,他们的异或值*/
    }

    int bit = XORResult & (~XORResult + 1);/*找到最末尾的一个bit1*/

    int num1 = 0;
    int num2 = 0;
    for(int i = 0; i < numsLen; i++)
    {
        if((nums[i] & bit) == 0)
        {
            num1 ^= nums[i];/*将比特位bit为0的所有元素异或*/
        }
        else {
            num2 ^= nums[i]; /*将比特位bit为1的所有元素异或*/
        }
    }

    int* result = (int*)malloc(2*sizeof(int));
    result[0] = num1;
    result[1] = num2;
    sort(&result[0],&result[1]);
    *returnSize = 2;

    return result;
}

算法图源于B站up:无尽的胖

以后有时间了自己再将详细过程画图补齐