1. Background
Let's look at the title first:
Title: 137. Once-only figures II
Difficulty: Medium
/problems/single-number-ii/
Given a nonempty array of integers, each element appears three times except for one element that appears only once. Find the element that appears only once.
Description:
Your algorithm should have linear time complexity. Can you implement it without using extra space?
Example 1.
importation: [2,2,3,2] exports: 3
Example 2.
importation: [0,1,0,1,0,1,99] exports: 99
Thoughts:
starting (point)result = 0For each bit, imagine each number as a 32-bit binary, and for each bit the binary 1's must add up to either 3N or 3N + 1 (occurring 3 times and 1 time); 3N means that the target value is not contributing to this bit, and 3N + 1 means that the target value is contributing to this bit (=1), and then all the contributing bits are recorded in theresultin. The advantage of this is that if the topic is changed to be the same as k, you only need to change the code tocount % kThat's it, very generic side-by-side going to each one.
2. C# Language
- Result: Adoption
- Execution time: 112 ms, beating 91.53% of all C# submissions
- Memory Consumption: 25.2 MB, beating 100.00% of all C# commits by users
public class Solution
{
public int SingleNumber(int[] nums)
{
int result = 0;
for (int i = 0; i < 32; i++)
{
int mask = 1 << i;
int count = 0;
for (int j = 0; j < ; j++)
{
if ((nums[j] & mask) != 0)
{
count++;
}
}
if (count % 3 != 0)
{
result |= mask;
}
}
return result;
}
}
3. Python language
class Solution:
def singleNumber(self, nums: List[int]) -> int:
result = 0
for i in range(32):
mask = 1 << i
count = 0
for num in nums:
if num & mask != 0:
count += 1
if count % 3 != 0:
result |= mask
return result
that amount or morePython code withC# The code logic is exactly the same, but an error is reported on commit. The error message is as follows:
importation：[-2,-2,1,1,-3,1,-3,-3,-4,-2] exports：4294967292 Expected results：-4
We found:
-4 The complement is 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1100
If the sign bit is not considered
1111 1111 1111 1111 1111 1111 1111 1100 -> 4294967292
C++, C#, Java, etc. have integers that are length-limited, e.g. byte 8-bit, int 32-bit, long 64-bit, but Python's integers are not length-limited (i.e., there's no high-bit overflow), so when the output is a negative number, it will result in it being thought of as a positive number! Because it thinks of 32-bit signed integers as unsigned integers, which is the pits.
We modify the above code by adding the judgment condition if result > 2 ** 31-1: Negative numbers beyond the range of 32-bit integersResult -= 2 ** 32The corresponding negative number can be obtained.
- Implementation results:pass (a bill or inspection etc)
- Execution time:96 ms, beating 19.00% of all Python3 submissions
-
Memory consumption:14.8 MB, beating 25.00% of all Python3 commits by users
class Solution:
def singleNumber(self, nums: List[int]) -> int:
result = 0
for i in range(32):
mask = 1 << i
count = 0
for num in nums:
if num & mask != 0:
count += 1
if count % 3 != 0:
result |= mask
if result > 2 ** 31-1:
result -= 2 ** 32
return result
4. Technical analysis
With the above question out of the way, let's dig a little deeper.
Integers exist in memory in complementary form, and the output is naturally in complementary form.
class Program
{
static void Main(string[] args)
{
string s1 = (-3, 2);
(s1);
// 11111111111111111111111111111101
string s2 = (-3, 16);
(s2);
// fffffffd
}
}
But let's see.Python (used form a nominal expression)bin() Output.
print(bin(3)) # 0b11 print(bin(-3)) # -0b11 print(bin(-3 & 0xffffffff)) # 0b11111111111111111111111111111101 print(bin(0xfffffffd)) # 0b11111111111111111111111111111101 print(0xfffffffd) # 4294967293
Isn't that cognitively upsetting, as we can see from the results:
-
PythonIf you bin a negative number (in decimal), the output is the binary representation of its original code plus a minus sign, a huge pit. -
PythonThe integers in are stored in complementary form. -
PythonMedium integers are not limited in length and do not overflow.
So in order to get the complement of a negative number (decimal representation), it is necessary to manually operate it with the hexadecimal number 0xffffffff by bit and then give it to bin() for output, and what you get is the complementary representation of the negative number.
Summary:
This graphic begins with aLeetcodeThe topic began to talk about, found that the C# language and Python language in the use of binary processing of integer data there are different, Python language does not belong to the strong type of language so do not limit the number of integer bits, on the surface seems to be convenient to use in fact is a pit. We should be more careful when using it.
Up to this point in this article on the topic ofPython Bitwise arithmetic pit-proof guide to this article, more related Python bitwise arithmetic pit-proof guide content please search for my previous articles or continue to browse the following related articles I hope you will support me more in the future!