当前位置：网站首页>LeetCode 260. Number III that appears only once

LeetCode 260. Number III that appears only once

2022-06-23 19:43:00 【51CTO】

So far I've written 500 Multiple algorithm problems , Some of them have been sorted into pdf file , At present, there are 1000 Multi page （ And it will continue to increase ）, You can download it for free

LeetCode 260. A number that appears only once III_LeetCode

Bit operation solution

Reference resources 《494, A number in which the solution of a bit operation occurs only once 》 LeetCode 260. A number that appears only once III_ A number that appears only once III_02

We see the XOR result on the far right 1, That's the red part , According to this position is 0 still 1 Divide the original array into two groups , that 13 and 17 Definitely not in the same group . So each group becomes a single number , The other numbers appear twice . Then we can use 《494, A number in which the solution of a bit operation occurs only once 》 The way to solve . The code is as follows

       
       public 
       
       int[] 
       
       singleNumber(
       
       int[] 
       
       nums) {
       
       int 
       
       bitmask 
       
       = 
       
       0;
       
       // XOR all the elements in the array 
       
       for (
       
       int 
       
       num : 
       
       nums) {
       
       bitmask 
       
       ^
       
       = 
       
       num;
       
    }
       
       // Because the result of XOR operation is not always 2 Of n The next power ,
       
       // There may be more than one in binary 1, For the sake of calculation 
       
       // We just need to keep any of them 1, Everything else is 
       
       // Let him become 0, What's left here is the one on the far right 1
       
       bitmask 
       
       &= 
       
       -
       
       bitmask;
       
       int[] 
       
       rets 
       
       = {
       
       0, 
       
       0};
       
       for (
       
       int 
       
       num : 
       
       nums) {
       
       // Then divide the array into two parts , Each part is in 
       
       // Or, respectively 
       
       if ((
       
       num 
       
       & 
       
       bitmask) 
       
       == 
       
       0) {
       
       rets[
       
       0] 
       
       ^
       
       = 
       
       num;
       
        } 
       
       else {
       
       rets[
       
       1] 
       
       ^
       
       = 
       
       num;
       
        }
       
    }
       
       return 
       
       rets;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.

The bit operations above bitmask &= -bitmask; It means to put bitmask The rightmost binary 1 Retain , All the other positions are changed to 0, Just find a data and print it

LeetCode 260. A number that appears only once III_ data _04