This is the fourth day of my participation in the August Text Challenge.More challenges in August

Title description:

136. Numbers that only appear once – LeetCode (leetcode-cn.com)

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

Description:

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

The sample a

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

Example 2

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

Thought analysis

There are two conditions in this problem

  1. Every element appears twice except one
  2. Your algorithm should have linear time complexity. Can you do it without using extra space?

Regardless of the second condition, there are various solutions, sorting violence, HashSet, HashMap, etc

But the spatial complexity of these solutions is too high

If the second condition is met, the xOR bit operation can be used.

The sorting method

slightly

HashMap

Using a HashMap to count the number of occurrences of an element in an array, key is the element, value is the number of occurrences, and finally we just need to find the key with value 1.

The code is relatively simple, skip.

HashSet

A HashSet has a feature that doesn’t allow you to add data to the HashSet twice, so to use this feature, we just need to go through and add data to the HashSet. If we fail to add data to the HashSet, we just need to delete the data from the HashSet. All that’s left, of course, is data that only appears once.

AC code

class Solution {
    fun singleNumber(nums: IntArray): Int {
        val set = mutableSetOf<Int> ()for (i in 0..nums.lastIndex) {
            if (!set.add(nums[i])) {
                set.remove(nums[i])
            }
        }
        return set.iterator().next()
    }
}
Copy the code

Bitwise xOR

Exclusive or solution: meet the exchange law of an exclusive or operation, a radius b radius radius a = a radius of a radius b = 0 b = a radius b radius radius a = a radius of a radius b = 0 b = a radius b radius radius a = a radius of a radius b = 0 b = b, therefore ans is equal to the nums [0] ^ nums [1] ^ nums [2] ^ nums [3] ^ nums [4]… And then, according to the commutation law, merge the equal ones together to xor (equal to 0), and then xor with the one that only appeared once, so that the result is that the one that only appeared once (0^ any value = any value)

AC code

class Solution {
    fun singleNumber(nums: IntArray) = nums.reduce() { a, b -> a.xor(b) }
}
Copy the code

conclusion

This problem is mainly in the second condition, space complexity requirements.

See the solution of the problem before you know the xOR solution.

So let’s sum up the xor here.

Xor operations have three properties.

  1. If you do xor with 0, you still get the same number, a⊕0=aa⊕0= AA ⊕0=a
  2. If you do the xor operation with itself, the result is 0, that is, a⊕a= 0A ⊕ A = 0A ⊕ A = 0A ⊕ A =0
  3. Satisfies commutative law and associative law exclusive or operation, namely the radius b radius radius a = a radius of a radius b = 0 b = ba radius radius b a = a radius of a radius b = 0 radius b = ba radius radius b a = a radius a radius b = 0 radius b = b

reference

Numbers that only appear once – Numbers that only appear once – LeetCode (leetcode-cn.com)

Learning algorithms, the result is less important than the process – numbers that only appear once – LeetCode (leetcode-cn.com)

Hash sets, bitwise xor operators – numbers that occur only once – LeetCode (leetcode-cn.com)

Occurrences of numbers only once (Java) – Occurrences of numbers only once – LeetCode (leetcode-cn.com)