异或：2进制相同为0，不同为1。同时满足交换律和结合律

  • 0 ^ N = N
  • N ^ N = 0

同或：2进制相同为1，不同为0

题一：如何不用额外遍历交换两个数

默认情况是使用临时变量来存储一个数，最后交换。在此处我们使用异或运算，依靠异或的下列特点来进行交换。

1
2
3
4
5
6
7
8
9
//默认情况
int tmp = a;
a = b;
b = tmp;

//依靠异或,但是条件是，A，B指向的是不同的内存区域
a = a ^ b;
b = a ^ b;
a = a ^ b;
  • 0 ^ N = N
  • N ^ N = 0

题二：一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并且打印这种数（LeetCode136）

默认情况是使用字典进行存储，将每种数作为键进行存储，值则为出现的次数，最后循环找到奇数次的那种数.

创建一个变量赋值为 0，使用该变量异或遍历每一个数组的值，即可。

1
2
3
4
5
6
7
8
9
10
11
static void Main(string[] args)
{
    int[] arrs = { 1, 1,2, 2, 4,2,4,6,5,5, 6,8,31,423, 8, 423, 31 };

    int eor = 0;
    for(int i = 0; i < arrs.Length; i++)
    {
        eor = eor ^ arrs[i];
    }
    Console.WriteLine(eor);
}

题三：怎么把一个int类型的数，提取出最右侧的1来。

例如：000001110101101111001101010101 ——->000000000000000000000000000001

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 static void Main(string[] args)
 {
     int a = 123456789;
     Print(a);
     int b = (a & (-a));
     Print(b);
 }

public static void Print(int num)
{
    for(int i = 31; i >= 0; i--)
    {
        Console.Write((num &(1<< i)) ==0?"0":"1");
    }
    Console.WriteLine();
}

题四：一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数（LeetCode260）

  1. 全员异或：通过遍历数组将所有元素异或，得到的结果eor1是两个目标数的异或值（因为相同数异或为 0，其他数成对出现被抵消）。
  2. 提取差异位：计算eor1 & (-eor1)得到2进制最右侧的 1，该位置代表两个目标数在此位上不同（一个为 0，一个为 1）。
  3. 分组异或：再次遍历数组，将元素分为两类：在该位为 1 的和为 0 的。由于其他数都是偶数次出现，分组后异或会抵消。而两个目标数因该位不同被分到不同组，最终eor2会得到其中一个目标数。
  4. 计算另一个数：用初始异或结果eor1异或eor2，即可得到另一个目标数。
  5. 时间复杂度O(n)，空间复杂度为 O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static void Main(string[] args)
{
   
    int[] arrs = {1, 1, 1, 2, 2, 4, 2, 4, 6, 5, 5, 6, 8, 31, 423, 8, 423, 31 };

    int eor1 = 0;
    for (int i = 0; i < arrs.Length; i++)
    {
       eor1 = eor1 ^ arrs[i];
    }
    int rightOne = (eor1 & (-eor1));
    int eor2 = 0;
    for(int i = 0; i < arrs.Length; i++)
    {
        if ((arrs[i] & rightOne) != 0)  //代表该数在这个位置有1.,此时则找到所有的在该位置上有1的数
        {
            eor2 = eor2 ^ arrs[i];   //将该数异或eor2，则得到其中的一个奇数次的数。
        }
    }
    int first = eor2;
    int second = eor1 ^ eor2;
    Console.WriteLine("2个数分别是"+first +"  "+ second);
}

题五：一个数组中有一种数出现K次，其他数都出现了M次，M>1,K<M，找到出现了K次的数，要求，额外空间复杂度O(1)，时间复杂度O(N)

  1. 初始化计数器数组：创建长度为 32 的数组t，用于统计每个二进制位（第 0 位到第 31 位）上 1 的出现总次数。

  2. 统计每位的出现次数：遍历数组中每个元素，对其每个二进制位进行判断：

    • 若元素的第i位为 1，则将t[i]加 1。

  3. 构建结果：遍历计数器数组t，对于每个二进制位i：

    • 若t[i]不是m的倍数（即t[i] % m != 0），说明该位在目标元素中为 1。

  4. 时间复杂度O(n)，空间复杂度 O(1)

    由于其他元素均出现m次，它们在每个二进制位上的贡献总和必然是m的倍数。而目标元素出现k次，其对应位的总次数为m的倍数 + k，因此通过取模运算可直接定位目标元素的二进制位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int onlyKTimes(int[] arr,int k,int m)
{
    int[] t = new int[32];
    foreach(int num in arr)//在此处是将数组中的所有的值以类似于2进制的类型存入数组当中，外层循环是遍历数组中的每个数，内层是将数变为2进制类型进行存储，t[0] = 此时外层循环的第一个值的右移0位，并且与1进行与运算，依此类推，t[1] = 右移一位与1与运算
    {
        for(int i = 0; i < 32; i++)
        {
            t[i] += (num>>i) & 1; //如果i位置的有1，则说明该数的2进制在这个位置有值
        }
    }
    int ans = 0;
    //：对于每个二进制位，如果其出现次数总和不是m的倍数，则该位在目标元素中为1
    for (int i = 0;i < 32; i++)
    {
        if (t[i] % m != 0)  //说明该位置存在出现k次的这种数
        {
            ans =ans|(1 << i); // 将第i位置为1，将 1左移i位，例如：00000000100000000
        }
    }
    return ans;
}