Title 1: the number I that occurs only once
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: 1.
Copy the codeExample 2:
Input:,1,2,1,2 [4]
Output: 4
Copy the codeMethod 1: bit XOR
/ * *
* @param {number[]} nums
* @return {number}
* /
var singleNumber = function(nums) {// The XOR operation satisfies the commutative and associative laws: A ⊕ B ⊕ A = (a⊕ A)⊕b = 0⊕b = b
let ans = 0;
for(const num of nums) {
ans ^= num; // 00000 0010 ^ 00000 0010 = 0000 0010
}
return ans;
};
Copy the codeMethod 2:
var singleNumber = function(nums) {
let set = new Set();
for(let i = 0 ,lenght = nums.length ; i< lenght ; i++ ) {
if(set.has(nums[i])) {
set.delete(nums[i]); // The second occurrence will be deleted
continue;
}
set.add(nums[i]);
}
return [...set];
};
Copy the codeTopic two: number II that occurs only once
Given an array of non-empty integers, every element appears three times except one. 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,3,2 [2]
Output: 3
Copy the codeExample 2:
Input:,1,0,1,0,1,99 [0]
Output: 99
Copy the codeMethod 1: loop +indexOf
/ * *
* @param {number[]} nums
* @return {number}
* /
var singleNumber = function(nums) {
for(leti=0; i<nums.length; ++i){
if(nums. IndexOf (nums [I], I + 1) = = 1 && nums. IndexOf (nums [I]) = = I) {/ / there is one
return nums[i]
}
}
};
Copy the codeMethod two: Sorting + math
/ * *
* @param {number[]} nums
* @return {number}
* /
var singleNumber = function(nums) {
nums.sort((a,b)=>a-b);
for(leti=0; i<nums.length; i+=3){
if(nums[i] ! = nums[i+1])return nums[i];
}
};
Copy the codeconclusion
- This type of problem can be solved with javascript syntax, or mathematically. There are no particularly good data structures and algorithms to solve it.