1. The subject

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?

Example 1:

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

Example 2:

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

1. Solution 1: Sort through again

/ * * *@param {number[]} nums
 * @return {number}* /
var singleNumber = function(nums) {
  nums.sort((pre, next) = > pre - next)
  const len = nums.length
  if(nums[0] !== nums[1]) {
    return nums[0]}if(nums[len - 2] !== nums[len - 1]) {
    return nums[len - 1]}for(let i = 1; i < len - 2; i++) {
   if(nums[i] ! == nums[i-1] && nums[i] ! == nums[i+1]) {
     return  nums[i]
   }
 }
};
Copy the code

Complexity analysis

  • Time complexity: O(nlogn) The complexity of the sorting algorithm is based on fast sorting
  • Space complexity: O(1).

2. Solution 2: XOR by bit

Because two identical numbers are bitwise or zero, then each number in the array is bitwise or lower, and the last number left is the number that occurs only once

/ * * *@param {number[]} nums
 * @return {number}* /
var singleNumber = function(nums) {
  let result = 0
  nums.forEach(num= > {
    result ^= num
  })
  return result
};
Copy the code

Complexity analysis

  • Time complexity: O(n)
  • Space complexity: O(1).