This is the 8th day of my participation in the First Challenge 2022

Topic describes

Leetcode Subject address

I’m going to give you an array of values, integers of type, one of which occurs only once, and all the other integers occur twice. Now you need to find the integer that appears once and return it.

Here’s an example:

arr: [1.2.1] return2

arr: [1.2.3.2.3] return1

arr: [2.2.3.4.3.5.4] return5
Copy the code

Thought analysis

The first way

This is to find elements that only appear once, and we can create a new object (or Map) to do the mapping

The value of the array is used as the key and 1 as the value. Each traversal determines whether the object has the key. If it does, 2 is used as the value.

If the value of the key is equal to 1, the value of the key is equal to 1.

The code is as follows:

/ * * *@param {number[]} nums
 * @return {number}* /
var singleNumber = function (nums) {
  const obj = {}
  for (let i = 0; i < nums.length; i++) {
    if (obj[nums[i]]) obj[nums[i]] = 2
    else obj[nums[i]] = 1
  }
  for (let key in obj) {
    if (obj[key] === 1) return key
  }
};
Copy the code

Here’s another requirement. If you can’t use the extra space, can you fulfill it?

The answer is yes.

The second way

Because there’s only one number that happens once, and all the others happen twice, so we sort the array, and if a number is not equal before and after it, we prove that it only happens once, right?

There’s a special case where you have to do the head and tail separately, because the head doesn’t have the preceding element, and the tail doesn’t have the following element.

In other cases, you just have to check if the elements are equal. Return if they are not equal.

The code is as follows:

/ * * *@param {number[]} nums
 * @return {number}* /
var singleNumber = function (nums) {
  nums.sort((a, b) = > a - b)
  // A special judgment is required
  for (let i = 0; i < nums.length; i++) {
    if ((i === 0&& nums[i] ! == nums[i +1]) || i === nums.length - 1 && nums[i - 1] !== nums[i]) return nums[i]
    if(nums[i] ! == nums[i -1] && nums[i] ! == nums[i +1]) return nums[i]
  }
};
Copy the code

The third way

The third method uses the xor operator (^).

Xor operators, which convert numbers into binary numbers and then compare them, 0 and 1 xor, which is 1, 1 and 1, or 0 and 0 xor, which is 0.

So two identical numbers, xor, return 0.

Because all the other numbers in our array appear twice, only one appears once. So we go through the array of xor, and the xor that occurs twice becomes zero, which is the same as the number that occurs and the xor that is zero, and returns the number itself.

The code is as follows:

/ * * *@param {number[]} nums
 * @return {number}* /
var singleNumber = function(nums) {
  let temp = 0;
  for (let i = 0; i < nums.length; i++)
    temp ^= nums[i];
  return temp;
}
Copy the code