This is the 13th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Numbers that occur only once (Question number 136)

The title

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

Description:

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

Example 1:

Input:2.2.1] output:1
Copy the code

Example 2:

Input:4.1.2.1.2] output:4
Copy the code

link

Leetcode-cn.com/problems/si…

explain

This one, this one is the classic Jane I hit (simple problem I punch).

But in the end the result was very embarrassing, Jane I failed.

Read the instructions carefully. There are two points:

  • Linear time complexity
  • No extra space is used

Linear time complexity is just order n, there’s nothing hard to understand, you can’t use extra space you can’t use extra variables, and that makes sense.

The general idea is to iterate once to get the result, and not use additional traverses to store the related content.

Because of this limitation, it’s obvious that you can’t use a normal hash and use a Map to remember the occurrence of a number. If the second occurrence is to remove the attribute from the Map and finally iterate through the entire array, the only attribute left on the Map is the final result.

The code is easy to write 👇 :

var singleNumber = function(nums) {
  const map = new Map(a)for (const num of nums) {
    if(! map.has(num)) { map.set(num,true)}else {
      map.delete(num)
    }
  }
  return [...map][0] [0]};Copy the code

Since this does not conform to the official instructions, it will not be put in the answer, here to take a look.

The only “linear” time complexity I can think of is to start at the beginning of the array and get the indexOf of the first element after the first position each time. If the indexOf of the number is not -1, then prove that the number exists twice, then update the array by removing the data at the beginning of the array and the position of the indexOf.

The operation is to remove two duplicate digits until you reach a number with indexOf of -1, which is the number that appears once, and if there is only one element left in the array, then the last digit left is the number that appears once.

The only problem with this approach is whether indexOf meets the specification for linear time complexity, and if not, then it does.

Your own answers (indexOf)

With that logic out of the way, 👇 look at the code:

var singleNumber = function(nums) {
  while (nums.length > 1) {
    const secondIndex = nums.indexOf(nums[0].1)
    if (secondIndex < 0) return nums[0]
    nums.splice(secondIndex, 1)
    nums.shift()
  }
  return nums[0]};Copy the code

The logic is pretty simple, but I don’t know if secondIndex counts as extra space, and I could have gotten rid of the variable name and mixed it up with the code below, but it might not be easy to understand, so I’ll just write it like this.

A Better way (XOR)

To tell you the truth, xor this method is really unexpected, remember the three characteristics of xor?

  1. A number XOR to 0 is equal to itself:A star 0 is equal to a
  2. A number XOR to itself equals 0:A star a is equal to 0
  3. The XOR operation satisfies the commutative and associative laws:A ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b

We can actually derive here, we can link all the numbers together using the xor operator, it could be something like this:

4 ^ 1 ^ 2 ^ 1 ^ 2
Copy the code

According to the commutative and associative laws, this expression can be written like this:

2 ^ 2 ^ 1 ^ 1 ^ 4
Copy the code

According to the second theorem above:

A number XOR with itself is equal to 0: a ⊕ a is equal to 0

We can replace the same number with zeros, so the formula looks like this:

0 ^ 0 ^ 4
Copy the code

After the transformation according to the second theorem, the formula becomes this:

0 ^ 4
Copy the code

Then apply the first theorem:

A number XOR with 0 is equal to itself: A ⊕ 0 = a

So you get to the point where this is actually going to be 4, which is the answer to this example.

You don’t have to worry about 0 and 0 xor, because whether it’s an odd 0 or an even 0, according to the second theorem, you’re going to end up with a 0, and you’re going to end up with a 0 and a number that appears once.

So the final solution is:

var singleNumber = function(nums) {
  return nums.reduce((a,b) = > a^b)
};

Copy the code

It’s hard to think of, so don’t try too hard.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)