Topic Description (Medium Difficulty)

Each number appears 3 times, and only one number appears 1. Find that number. The time complexity is O (n) and the space complexity is O (1).

You can take a look at problem 136 first, and think about it completely in terms of each solution.

Method a

Let’s ignore the space and do it the conventional way.

You can count each number with a HashMap and return the number of 1.

public int singleNumber(int[] nums) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(nums[i])) {
            map.put(nums[i], map.get(nums[i]) + 1);
        } else {
            map.put(nums[i], 1); }}for (Integer key : map.keySet()) { 
        if (map.get(key) == 1) {
            returnkey; }}return -1; // This sentence will not be executed
}
Copy the code

Time complexity: O (n).

Space complexity: O (n).

Solution 2 mathematical derivation

Remember what we did on problem 136, where each number appears twice and only one number appears once.

Let’s say our numbers are a, B, A, B, C, C, and D

So how do we figure out d?

You just add up all the numbers that appear, multiply by 2, and subtract the sum of the previous numbers.

What does that mean?

The numbers in the example above are a, B, C, and D, and if you multiply them by two, you get 2 times a plus b plus c plus D. The sum of the previous numbers is a plus b plus a plus b plus c plus c plus D.

(a + b + c + d) – (a + b + a + b + c + c + d)

After reading this solution I can only say TQL…

To find out what number was present, all we need is a Set to duplicate it.

Here each number appears 3 times, so we can add it up times 3 and subtract the sum of all the previous numbers. So the difference is twice as big as the one that only happened once.

public int singleNumber(int[] nums) {
    HashSet<Integer> set = new HashSet<>();
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        set.add(nums[i]);
        sum += nums[i];
    }
    int sumMul = 0;
    for (int n : set) {
        sumMul += n;
    }
    sumMul = sumMul * 3;
    return (sumMul - sum) / 2;
}
Copy the code

But it didn’t pass

Int is a 32-bit integer, which is represented by a complement code. The fundamental problem is that if 2a is equal to c, then there are two cases for what a can be. In the absence of overflow, a = c/2 is fine. But if a is a big number, they add up and overflow, then a = c >>> 1.

To give you a specific example,

If the given array is [1 1 1 Integer.maxValue]. And if you do that, what you end up with is zero

(1 + Ingeger.MaxValue) * 3 - (1 + 1 + 1 + Integer.MaxValue) = 2 * Integer.MaxValue

Because of the overflow

2 * integer. MaxValue = -2, and we return -2/2 = -1.

So this idea doesn’t work, because you don’t know if it’s going to overflow.

Solution three digit operation

136. The problem is solved by either or.

Let’s look at numbers in binary form

Let's say the example is1 2 6 1 1 2 2 3 3 3.3 个 1.3 个 2.3 个 3.1 个 6
1 0 0 1
2 0 1 0 
6 1 1 0 
1 0 0 1
1 0 0 1
2 0 1 0
2 0 1 0
3 0 1 1  
3 0 1 1
3 0 1 1Look at the right-hand column1001100111 有 6 个 1Let's go one more column0110011111 有 7 个 1Let's go one more column0010000 有 1 个 1We just need to get the3Write the corresponding column of multiples of0, not3Write the corresponding column of multiples of1That is1 1 0, that is,6.Copy the code

It’s easy to see why. If all numbers appear three times, then the number of 1s in each column must be a multiple of 3. The only reason a column isn’t a multiple of 3 is because it only happens once and it contributes 1. So all the columns that are not multiples of 3 are 1, and all the other columns are 0, and you find this number that occurs once.

public int singleNumber(int[] nums) {
    int ans = 0;
    // Consider each digit
    for (int i = 0; i < 32; i++) {
        int count = 0;
        // Consider each number
        for (int j = 0; j < nums.length; j++) {
            // Whether the current bit is 1
            if ((nums[j] >>> i & 1) = =1) { count++; }}// The number of 1 is a multiple of 3
        if (count % 3! =0) {
            ans = ans | 1<< i; }}return ans;
}

Copy the code

Time complexity: O (n).

Space complexity: O (1).

Solution four general methods

See here.

In solution three, we convert the numbers to binary and count the number of 1s in each digit. We use a 32-bit int to count. In fact, we just need to see if it’s a multiple of 3, so we only need two bits. We initialize it to 00, we change it to 01 on the first 1, we change it to 10 on the second 1, we change it back to 00 on the third 1. Then you need to figure out how to do it.

Originally wanted to write according to their own understanding of the train of thought, but here to write very good, mainly or translation.

Generalize the problem

Given an array where each element occurs k (k > 1) times, except for a number that occurs only P times (p >= 1, p % k! =0), find the number that occurs p times.

Consider one of the bits

In order to counterkTime, we have tomOne bit, where, that is,m >= logk.

Suppose wemThe bits are in order 。

I’m going to initialize everything to zero. 00… 00.

The current bit of all numbers is then scanned, with I representing the current bit.

That’s one of the columns in solution three.

Let's say the example is1 2 6 1 1 2 2 3 3 3.3 个 1.3 个 2.3 个 3.1 个 6
1 0 0 1
2 0 1 0 
6 1 1 0 
1 0 0 1
1 0 0 1
2 0 1 0
2 0 1 0
3 0 1 1  
3 0 1 1
3 0 1 1   
Copy the code

Initial status 00… 00.

The first time you encounter 1, the m bits are 00… 01.

The second time I encounter 1, the m bits are 00… 10.

On the third encounter with 1, the m bits are 00… 11.

On the fourth encounter with 1, the m bits are 00.. 100.

X1 goes to 1 when it hits 1, and goes back to 0 when it hits 1. It doesn’t change if you hit 0.

So x1 is equal to x1 to the I, and you can use xor to solve for x1.

So the x2… What about XM?

X2, when you hit 1, if x1 was 0 before, x2 stays the same. If x1 was 1 before, that corresponds to the second encounter up here and the fourth encounter up here. X2 goes from 0 to 1 and from 1 to 0.

So the way x2 is going to change is if you hit 1 and x1 is 1, and if you hit 1 and x1 is 1 you go back to 0. It doesn’t change if you hit 0. It’s very similar to x1, so you can use xor as well.

X2 is equal to x2 to the I ^ x1, which tells me if x1 is 1.

The x3 and x4… Xm is the same thing, xm = xm ^ (xm-1 &… &x1 &i).

And to get straight to the point, it actually simulates the change in the bits each time you increment by 1. So high xM only gets carried 1 if all low xm gets carried 1.

00 -> 01 -> 10 -> 11 -> 00

There’s a problem up there, assuming our k is equal to 3, then we should go to 00 after 10, not 11.

So we need a mask, and the operation with mask is itself when it does not reach k, and when it reaches K it goes back to 00… 000.

Construct the mask according to the above requirements, assuming k is written in binary is km… K2k1.

mask = ~(y1 & y2 & ... & ym),

If KJ is equal to 1, then yj is equal to xj

If KJ is equal to 0, yj is equal to xj.

Here are two examples.

K = 3: write binary, k1 = 1, k2 = 1, mask = ~(x1 & x2);

K = 5: write binary, k1 = 1, k2 = 0, k3 = 1, mask = ~(x1 & ~x2 & x3);

It’s easy to figure out when x1x2… Xm to k1k2… Km because we’re going to take x1x2… Xm to zero. We just have to do the sum operation with 0 and each digit to get back to 0.

So all we have to do is take the bits that are equal to 0 and then add them to everything else and you get 1, and then take the bits that are equal to 0.

If x1x2… Xm does not reach K1K2… Km, then the result must be 1, so the operation with the original bit will keep the original number.

Anyway, at the end of the day our code is the framework below.

for (int i : nums) {
    xm ^= (xm-1&... & x1 & i); xm-1 ^= (xm-2&... & x1 & i); . x1 ^= i; mask = ~(y1 & y2 & ... & ym) where yj = xjif kj = 1, and yj = ~xj if kj = 0 (j = 1to m). xm &= mask; . x1 &= mask; }Copy the code

Consider all bits

Let's say the example is1 2 6 1 1 2 2 3 3 3.3 个 1.3 个 2.3 个 3.1 个 6
1 0 0 1
2 0 1 0 
6 1 1 0 
1 0 0 1
1 0 0 1
2 0 1 0
2 0 1 0
3 0 1 1  
3 0 1 1
3 0 1 1   
Copy the code

We’ve done one bit, that is, each column. Because we gave it an int, it has 32 bits. So we need to count each digit. With this analysis, we don’t have to look at each bit in turn as we did in solution three, we can count 32 bits at the same time.

For k equals 3, that’s this problem. We can use two ints, x1 and x2. X1 represents the low value of each 32-bit count, x2 represents the high value of each 32-bit count. Using the previous formula, we can do the counting at the same time using the bit operation.

int x1 = 0, x2 = 0, mask = 0;

for (int i : nums) {
    x2 ^= x1 & i;
    x1 ^= i;
    mask = ~(x1 & x2);
    x2 &= mask;
    x1 &= mask;
}
Copy the code

What return

Last question, what do we need to return?

In solution 3, we see if the number of occurrences of 1 is a multiple of 3, and if it is not a multiple of 3, it will correspond to position 1.

It’s the same thing here, because all the numbers appear k times, and only one number appears P times.

Because xm… X2x1 combined is the count of 1 for each column. For example

Let's say the example is1 2 6 1 1 2 2 3 3 3.3 个 1.3 个 2.3 个 3.1 个 6
1 0 0 1
2 0 1 0 
6 1 1 0 
1 0 0 1
1 0 0 1
2 0 1 0
2 0 1 0
3 0 1 1  
3 0 1 1
3 0 1 1Look at the right-hand column1001100111 有 6 个 1, that is,110Let's go one more column0110011111 有 7 个 1, that is,111Let's go one more column0010000 有 1 个 1, that is,001X1, x2, x3 is x11 1 0
x2 0 1 1
x3 0 1 1
Copy the code

If p is equal to 1, then if any of the digits that occur once are 1, then x1, the lowest digit of the count, must be 1, so let’s just return x1. For the example above, it’s 110, so return 6.

If p is equal to 2, binary is 10, so if one of the digits that occurs twice is 1, it must make the corresponding digit for x2 1, so we just return x2.

If p = 3, binary is 11, so if one of the three digits is 1, it must make the corresponding x1 and x2 bits 1, so we can just return x1 or x2.

So there you have the code for this problem

public int singleNumber(int[] nums) {
    int x1 = 0, x2 = 0, mask = 0;
    for (int i : nums) {
        x2 ^= x1 & i;
        x1 ^= i;
        mask = ~(x1 & x2);
        x2 &= mask;
        x1 &= mask;
    }
    return x1; 
}
Copy the code

And the reason why X2 is xor and then X1 is because x2 depends on the state before X1. The reverse is clearly wrong.

And just to expand the problem a little bit, what do we do with k = 5 and p = 3, so each number appears five times, and only one number appears three times.

First of all, k is equal to 5, so we need at least 3 bits. Because two bits count up to four times.

Then the binary form of k is 101, so mask = ~(x1 & ~x2 & x3).

The binary of P is 011, so we can finally return x1.

public int singleNumber(int[] nums) {
    int x1 = 0, x2 = 0, x3  = 0, mask = 0;
    for (int i : nums) {
        x3 ^= x2 & x1 & i;
        x2 ^= x1 & i;
        x1 ^= i;
        mask = ~(x1 & ~x2 & x3);
        x3 &= mask;
        x2 &= mask;
        x1 &= mask;
    }
    return x1;  
}
Copy the code

Problem 136, k = 2, p = 1, is actually of this type. But since k = 2 and when we count with one bit, it automatically returns to zero at 2, we don’t need a mask and it’s relatively easy.

public int singleNumber(int[] nums) {
    int x1 = 0;

    for (int i : nums) {
        x1 ^= i;
    }

    return x1;
}
Copy the code

This solution is really too strong, completely back to the binary operation, completely comfortable, recommend to look at the original English analysis, too strong.

The total

The first solution uses HashMap counting to be very common, while the second solution fails to pass the mathematical formula, but the overflow problem is also something we often need to consider. Solution three If you look at the numbers in binary, the number of ones is pretty strong. Solution four directly use the bit bit to count, is really an eye-opener, fairy operation.

See Leetcode.Wang for more details on popular problems.