Press the missing number of interview question 17.04 | | 260. the number that appears only once (including bit operation knowledge points)

Title Missing numbers || A number that appears only once

---

Catalog

Title Missing numbers || A number that appears only once

1. subject Missing numbers

1.2. Topic analysis

 1.3. Question answer

 2. subject A number that appears only once

2.2. Topic analysis

2.3. Question answer

3. Topic knowledge

3.1 Bit operator exclusive or ^

3.1 Shift right operator

---

---

Recommended reading order :

1. subject ->3. answer ->2. Topic analysis ->4. Topic knowledge

---

1. subject Missing numbers

Interview questions 17.04. Missing numbers - Power button （LeetCode）https://leetcode.cn/problems/missing-number-lcci/submissions/

1、 Array nums Contains from 0 To n All integers of , But one of them is missing . Please write code to find the missing integer . You have a way O(n) Is it finished in time ？

Be careful ： A slight change in the title of the book

Example 1：

Input ：[3,0,1]
Output ：2

Example 2：

Input ：[9,6,4,2,3,5,7,0,1]
Output ：8

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

---

1.2. Topic analysis

It's better to watch by number

---

 1.3. Question answer

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. subject A number that appears only once

260. A number that appears only once III - Power button （LeetCode）

Given an array of integers  nums, There are exactly two elements that only appear once , All the other elements appear twice . Find the two elements that only appear once . You can press In any order Return to the answer .

Advanced ： Your algorithm should have linear time complexity . Can you just use constant space complexity to achieve ？

Example 1：

Input ：nums = [1,2,1,3,2,5]
Output ：[3,5]
explain ：[5, 3] It's also a valid answer .
Example 2：

Input ：nums = [-1,0]
Output ：[-1,0]
Example 3：

Input ：nums = [0,1]
Output ：[1,0]
Tips ：

2 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
Except for two integers that appear only once ,nums The other numbers in appear twice

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

}

---

2.2. Topic analysis

It's better to watch by number

---

2.3. Question answer

/**
 * 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;
    // First all XOR 
    for(i=0;i<numsSize;i++)
    {
        ret ^=nums[i];
    }
    // Calculate which one is 1
    int pos=0;
    for(pos=0;pos<32;pos++)
    {
        if((ret>>pos&1)==1)
        {
            break;
        }
    }
    // grouping 
    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. Topic knowledge

3.1 Bit operator exclusive or ^

Several laws of XOR operation ：

0. Same as 0, Dissimilarity is 1

1. 0 XOR with any value equals itself , namely ：A ^ 0 = A

2. XOR itself equals 0, namely A ^ A = 0

3. XOR satisfies the law of association , namely A ^ B ^ C = A ^ ( B ^ C)、

4. XOR satisfies the law of exchange , namely A^B=B^A

5. One number and two identical numbers are exclusive or , Finally get itself A^B^A=A^A^B=0^B=B

3.1 Shift right operator

1. Logical shift Use... On the left 0 fill , On the right side of the discarded

2. Arithmetic shift The left is filled with the sign bit of the original value , On the right side of the discarded

tips:

You can move right one bit at a time and press... At the same time 1 To judge whether this bit is binary 1.

---

Hello everyone ！ This is Yuanzai ！^-^ I hope this sharing is helpful to you , You are also welcome to subscribe to my topic sharing column , Here will share some experience summary of wrong questions from time to time , If there is something wrong in sharing , Welcome to tell Yuanzai in time ！！ I wish you happy every day , See you next time ！！