[数据结构与算法][LeetCode]-刷题--1.消失的数字--2.

目录

1.消失的数字

链接：https://leetcode-cn.com/problems/missing-number-lcci/

题解：

?2.只出现一次的数

链接：https://leetcode-cn.com/problems/single-number-iii/

题解：

小心这个测试用例[1,1,0,-2147483648]

1.消失的数字

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

• 示例 1：
• 输入：[3,0,1] 输出：2
• 示例 2：
• 输入：[9,6,4,2,3,5,7,0,1] 输出：8

链接：力扣https://leetcode-cn.com/problems/missing-number-lcci/

题解：

比如 输入：[9,6,4,2,3,5,7,0,1] 0到9 缺个8，所以一共有9个数，将这9个数全部异或

然后再for（0到9）在异或，两个相同异或为0；最后结果就是消失的数。

int missingNumber(int* nums, int numsSize){
int ret=0;
for(int i=0;i<numsSize;i++)//一共有numsSize个数,缺一个8，所以数组0到<numsSize）全部异或
{
   ret^=nums[i];

}
for(int j=0;j<=numsSize;j++)//（<=numsSize全部异或）
{
    ret^=j;
}
printf("%d ",ret);
return 0;
}

?2.只出现一次的数

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

链接：https://leetcode-cn.com/problems/single-number-iii/

题解：

将所有的数全部异或，最后就是3^5的值；在二进制中他们肯定有一位时不同的；所以先找出不同的那位，然后进行分组，最后就是两个不同的值，

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* singleNumber(int* nums, int numsSize, int* returnSize){
int ret=0;
for(int i=0;i<numsSize;i++)
{
  ret^=nums[i];//全部异或
}
int m=0;
while(m<=31)
{
    if(ret & (1<<m))//找出二进制不同那位
    {
        break;
    }
    else
    {
    m++;
    }
}
int x=0,y=0;
for(int j=0;j<numsSize;j++)//进行分组
{
   if(nums[j]&(1<<m))
   {
       x^=nums[j];
   }
   else{
       y^=nums[j];
   }

}
int *arr=(int *)malloc(sizeof(int)*2);//分配空间
arr[0]=x;
arr[1]=y;
*returnSize=2;

return arr;

}

小心这个测试用例[1,1,0,-2147483648]

int* singleNumber(int* nums, int numsSize, int* returnSize){
    int temp = 0,bit1 = 1;
    int num1 = 0, num2 = 0;
    int* ret;
    // 将所有数据进行异或，最终temp中的结果就相当于是两个只出现一次的数据进行异或
    for(int i = 0; i < numsSize; ++i)
    {
        temp ^= nums[i];
    }

    // 找到temp中第一个为1的比特位，说明两个只出现一次的数据在该位上一定是1
    // [1,1,0,-2147483648]  小心这个测试用例
    // 与完之后 temp中为-2147483648  取反的话结果就溢出了
    long long mask = temp&(-(long long)temp);

    for(int i = 0; i < numsSize; ++i)
    {
        if(nums[i]&mask)
        {
            num1 ^= nums[i];
        }
        else
        {
            num2 ^= nums[i];
        }
    }

    ret = (int*)malloc(sizeof(int)*2);
    ret[0] = num1;
    ret[1] = num2;
    *returnSize = 2;
    return ret;
}