Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

I. Problem description

Given an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once.

Note: Your algorithm should have linear time complexity. Can you do it without using extra space?

Title link: a number that appears only once.

Two, the title requirements

Sample 1

Input: [2,2,1] output: 1Copy the code

The sample 2

Input: [4,1,2, 2] Output: 4Copy the code

inspection

1. Bit operation xOR, double pointer, mathematical thought 2Copy the code

Third, problem analysis

1. What is the meaning of bitwise operation?

Day 45: Bit operation.

1. Double pointer

At first, I wanted to sort the array from smallest to largest. Here are two examples, sorted as follows:

1 2 1 2 3 4 1 2 3 two contrast, because sorting after equal number gather together, if not equal to the output, OK!Copy the code
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int i=0,j=1,n=nums.size(a);// double pointer I j
        sort(nums.begin(),nums.end());/ / sorting
        while(i<n&&j<n)
        {
            if(nums[i]! =nums[j])/ / not equal
            {
                return nums[i];// Return the result directly
            }
            i+=2,j+=2;// Go back two
        }
        return nums[n- 1];// Print the last one}};Copy the code

2. Bit operations

Bit operation at first true unexpectedly, after looking at the solution found that the solution is very clever.

This article has a detailed explanation, so I will give a general overview.

The xOR operation satisfies the commutative and associative laws, such as:

1^2^1^2 = 1^1^2^2^4 = 0^0^4 = 4Copy the code

It turns out to be the last number that didn’t cancel.

Four, coding implementation

class Solution {
public:
    int singleNumber(vector<int>& nums) {
       int i=0,n=nums.size(a);/ / initialization
       for(i=1; i<n; i++) { nums[i]=nums[i]^nums[i- 1];// xor start
       }
       return nums[n- 1];// Output the result
};
Copy the code

V. Test results