The title

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 be a linear time complexity, can you implement it without extra space?

The sample

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

The sample

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

Routine search

If the requirements are not specified, the solution that immediately comes to mind may be:

  • Arr [I] = arr[I] = arr[I] == arr[I +1] is equal
  • Some of you might have thought of using objects to store the number of occurrences, which is great
  • The other thing that’s not easy to think about is the xor operation, where the same is false and the different is true

implementation

Sorting implementation

function singleNumber(arr) {
  arr.sort()
  const len = arr.length
  for (let i = 0; i < len ; i = i + 2) {
    if (i + 1 >= len ) {
        return arr[i];
    }
    if(arr[i] ! = arr[i + 1]) {returnarr[i]; }}return1}Copy the code

A hashMap stores the number of occurrences of a value

Time complexity: O(n) Space complexity: O(n)

function singleNumber(arr){
  const sum = {}
  for (let i = 0; i < arr.length; i++) {
    if(! sum[arr[i]]) { sum[arr[i]] = 0 } sum[arr[i]]++ } const newVal = Object.keys(sum)for (let i = 0; i < newVal.length; i++) {
    if (sum[newVal[i]] === 1) {
      return newVal[i]
    }
  }
  return1}Copy the code

Clever use of the xor operator, when two values are the same xor result is 0

function singleNumber(arr){
  for (let i = 1; i < arr.length; i++) {
    arr[0] ^= arr[i]
  }
  return arr[0]
}
Copy the code

conclusion

  • A number that appears only once
  • The ^ operator