This is the sixth day of my participation in the August More text Challenge. For details, see: August More Text Challenge
The number of times a number appears in an array
Offer 56-i. Number of times the number of digits in the array
Difficulty: Medium
Topic: leetcode-cn.com/problems/sh…
All but two digits appear twice in an integer array nums. Write a program to find these two numbers that only appear once. The time complexity is O(N), and the space complexity is O(1).
Example 1:
Input: nums = [4,1,4,6] output: [1,6] or [6,1]Copy the codeExample 2:
Input: nums = [1,2,10,4,1,4,3] output: [2,10] or [10,2]Copy the codeRestriction: 2 <= convent. length <= 10000
Answer key
If the time complexity is O(N) and the space complexity is O(1), it cannot be done by brute force or table building.
An operation
The xOR method can be used to determine whether two elements in an array are the same.
A ⊕a⊕b⊕b⊕c = 0⊕0⊕c = c for an array with only one distinct element: a⊕a⊕b⊕b⊕c = 0⊕0⊕c = c
// @params nums[]
var singleNumber = (nums) = > {
let x = 0;
for (let num of nums) {
x ^= num;
}
return x;
}
console.log(singleNumber([2.2.4.5.4])) / / 5
Copy the codeHowever, in this case, the non-repeating number appears twice, so we need to simplify it by following the steps:
-
Iterating OVER NUMS performs xor, as a⊕a⊕b⊕b⊕c⊕d = 0⊕0⊕c⊕d = c⊕d.
-
If c⊕d some bit is 1, then the bits of C and D must be different, and we can divide the array into two subarrays based on bit 1, with only one distinct number in each array. Such as:
For [1,2,10,4,1,4,3,3],2 and 10 are non-repeating numbers, then
2 – > 0010; 10 – > 1010; The first digit of two binary numbers, 2 and 10, is different. 2 and 10 give 8 -> 1000, that is, divide the two subarrays by 8.
-
Split NUMs into two subarrays.
-
Iterating over the two subarrays separately performs xOR, which decouples the problem and returns the xor value of the two subarrays.
/ * * *@param {number[]} nums
* @return {number[]}* /
var singleNumbers = function (nums) {
let x = 0.// Subarray 1 is not a duplicate number
y = 0.// Subarray 2 is not a duplicate number
n = 0.// Used to partition arrays
m = 1; // Used to partition arrays
// 1. Traversal xOR
for (let num of nums) {
n ^= num;
}
// 2. Rotate to the left to calculate m
while ((n & m) === 0)
m <<= 1;
/ / 3. Draw molecules array (num & m) = = = 1 and (num & m) = = = 0, must add brackets!
for (let num of nums) {
if((num & m) ! = =0) x ^= num; // 4. Subarray XOR
else y ^= num;
}
return [x, y]; // Return the result
};
/ / the console. The log (singleNumbers (,2,10,4,1,4,3,3 [1]))
Copy the code- Time complexity: O(N)
- Space complexity: O(1)
The number of occurrences of numbers in the array II
Offer 56-ii. number of times in the array II
Difficulty: Medium
Topic: leetcode-cn.com/problems/sh…
Every number in an array nums appears three times except for one that appears only once. Please find the number that appears only once.
Example 1:
Input: nums = [3,4,3,3] output: 4Copy the codeExample 2:
Input: nums = [9,1,7,9,7,9,7] output: 1Copy the codeAnswer key
Method one hash table
Walk through the group, counting the number of occurrences of each number, and finally walk through the hash table again, returning the value with the number of occurrences of 1.
/ * * *@param {number[]} nums
* @return {number}* /
var singleNumber = function (nums) {
const map = new Map(a);// Count the number of occurrences of each number
for (let num of nums) {
if (map.has(num)) {
map.set(num, map.get(num) + 1);
} else {
map.set(num, 1); }}// Iterate through the hash table to find values that occur 1 times
for (let [_, value] of map.entries()) {
if (value === 1) returnvalue; }};//console.log(singleNumber([9, 1, 7, 9, 7, 9, 7]))
Copy the code- Time complexity: O(N)
- Space complexity: O(N)
Method two mathematical formula method
If a and b occur three times and C occurs once in a, B and C, then 3*(a+b+c)-(3*a+3*b+c) = 2c can be used to calculate the value of C.
To record and deduplicate all the values in an array, you can use a Set.
var singleNumber = function (nums) {
// 1. Deduplicate the array
let set = new Set(nums);
let sum1 = 0,
sum2 = 0
// 设置sum1，为例子中的(a+b+c)
for (let num of set) {
sum1 += num;
}
// 设置sum2，为例子中的(3*a+3*b+c)
for (let num of nums) {
sum2 += num;
}
// Return the result
return Math.floor((3 * sum1 - sum2) / 2)}Copy the code- Time complexity: O(N)
- Space complexity: O(N)
Method three bit operation
We can’t do xOR like we did last time, but we can do bit operations.
If a number appears three times, each bit of the binary representation also appears three times. If you add up each bit of the binary representation of all the numbers that occur three times, the sum of each bit is divisible by 3. If the sum of a digit is divisible by 3, then the binary representation of the digit that appears only once is 0; Otherwise it’s just 1.
The appeal idea also applies to an array where one number occurs once and the other numbers occur an odd number of times (if it is an even number, use xor directly).
Steps:
- Setting initial values
- Add and to every number and mask in the array, incrementing count by 1 if the result is not zero
- If count goes into 3, it’s not a one-time number
var singleNumber = function (nums) {
let res = 0;
// The highest binary bit is 32 bits
for (let bit = 0; bit < 32; bit++) {
let mask = 1 << bit;
let count = 0;
for (let num of nums) {
if (num & mask) count++;
}
if (count % 3) { res = res | mask; }}return res;
}
Copy the code- Time complexity: O(N)
- Space complexity: O(1)