力扣面试题17.04 消失的数字||260.只出现一次的数字（内含位运算知识点）

题目名称 消失的数字||只出现一次的数字

---

目录

题目名称 消失的数字||只出现一次的数字

1.题目 消失的数字

1.2.题目分析

 1.3.题目答案

 2.题目 只出现一次的数字

2.2.题目分析

2.3.题目答案

3.题目知识点

3.1位运算符异或^

3.1右移操作符

---

---

推荐阅读顺序:

1.题目->3.答案->2.题目分析->4.题目知识点

---

1.题目 消失的数字

面试题 17.04. 消失的数字 - 力扣（LeetCode）https://leetcode.cn/problems/missing-number-lcci/submissions/

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

注意：本题相对书上原题稍作改动

示例 1：

输入：[3,0,1]
输出：2

示例 2：

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

int missingNumber(int* nums, int numsSize)
{
    
}

---

1.2.题目分析

按数字编号观看更佳

---

 1.3.题目答案

int missingNumber(int* nums, int numsSize)
{
    int i=0;
    int mis=0;
    for(i=0;i<numsSize;i++)
    {
        mis=mis^i;
        mis=mis^nums[i];
    }
    mis=mis^numsSize;
    return mis;
}

---

 2.题目 只出现一次的数字

260. 只出现一次的数字 III - 力扣（LeetCode）

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

示例 1：

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

输入：nums = [-1,0]
输出：[-1,0]
示例 3：

输入：nums = [0,1]
输出：[1,0]
提示：

2 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
除两个只出现一次的整数外，nums 中的其他数字都出现两次

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* singleNumber(int* nums, int numsSize, int* returnSize){

}

---

2.2.题目分析

按数字编号观看更佳

---

2.3.题目答案

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* singleNumber(int* nums, int numsSize, int* returnSize)
{
    int ret =0;
    int i=0;
    //先全体异或
    for(i=0;i<numsSize;i++)
    {
        ret ^=nums[i];
    }
    //计算哪一位为1
    int pos=0;
    for(pos=0;pos<32;pos++)
    {
        if((ret>>pos&1)==1)
        {
            break;
        }
    }
    //分组
    int p1=0,p2=0;
    for(i=0;i<numsSize;i++)
    {
        if((nums[i]>>pos&1)==1)
        {
            p1^=nums[i];
        }
        else
        {
            p2^=nums[i];
        }
    }
   nums[0]=p1;
   nums[1]=p2;
   *returnSize=2;
    return nums;

}

---

3.题目知识点

3.1位运算符异或^

异或运算的几条规律：

0.相同为0，相异为1

1. 0和任何值的异或等于本身，即：A ^ 0 = A

2. 异或本身等于0，即 A ^ A = 0

3. 异或满足结合律，即 A ^ B ^ C = A ^ ( B ^ C)、

4.异或满足交换律，即A^B=B^A

5.一个数字和两个相同的数字异或，最后得到它本身A^B^A=A^A^B=0^B=B

3.1右移操作符

1. 逻辑移位 左边用0填充，右边丢弃

2. 算术移位 左边用原该值的符号位填充，右边丢弃

tips:

可以通过每次右移一位同时按位与1来判断这一位二进制是不是1。

---

大家好！这里是媛仔！^-^希望这篇分享对你有所帮助，也欢迎大家订阅我的题目分享栏目，这里会不定时的分享一些错题经验总结，如果在分享中有什么出错的地方，欢迎及时的告诉媛仔！！祝你天天开心，下期见！！