中国的网络营销公司_建筑设计公司名称起名_台州seo排名扣费_日本搜索引擎

文章目录

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！

👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++算法感兴趣的朋友，让我们一起进步！

1. C++ 位运算算法详解

1.1 位运算的重要性

位运算（Bitwise Operation）是计算机底层操作的核心。它的重要性体现在以下几个方面：

高效性：位运算直接操作二进制位，速度极快，是最高效的运算方式之一。
底层控制：用于硬件控制、网络协议、图像处理等领域，帮助开发者操作底层数据。
空间优化：在数据压缩、哈希算法等场景中，通过位操作极大节省存储空间。
算法核心：许多高效算法依赖位运算实现，比如快速幂、判断奇偶、位图等。

1.2 位运算的定义

位运算是对整数在二进制位层面进行操作的运算，主要包括以下基本操作：

按位与（&）
- 规则：两个二进制位都为 1 时，结果为 1；否则为 0。
- 应用：常用于掩码操作，保留某些位的信息。
  - 示例：1101 & 1011 = 1001
按位或（|）
- 规则：只要有一个二进制位为 1，结果为 1；否则为 0。
- 应用：设置某些位为 1。
  - 示例：1101 | 1011 = 1111
按位异或（^）
- 规则：二进制位相同为 0，不同为 1。
- 应用：交换值、检测位差。
  - 示例：1101 ^ 1011 = 0110
按位取反（~）
- 规则：将每个位取反，即 1 变 0，0 变 1。
- 应用：构造补码。
  - 示例：~1101 = 0010（假设为4位操作）
左移（<<）
- 规则：将所有位向左移动指定位置，右边补 0。
- 应用：高效计算乘以 2^n。
  - 示例：1101 << 2 = 110100
右移（>>）
- 规则：将所有位向右移动指定位置。
  - 算术右移：高位用符号位填充，保留符号。
  - 逻辑右移：高位用 0 填充。
- 应用：高效计算除以 2^n。
  - 示例：1101 >> 2 = 0011

1.3 位运算的核心思想

二进制数据的直接操作：将复杂的逻辑转换为简单的二进制运算。
高效替代算术操作：使用移位、与或操作完成加减乘除或逻辑控制。
灵活的位级处理：针对数据的某些特定位进行精确控制和修改。
组合运用：通过多种位运算的结合，构造高效的算法。

1.4 经典应用

快速判断奇偶数
- 思路：通过按位与操作 n & 1 判断奇偶。
  - 示例：5 & 1 = 1（奇数），4 & 1 = 0（偶数）
交换两个数（不使用额外变量）

a = a ^ b b = a ^ b a = a ^ b
- 示例：a = 5, b = 7 -> a = 7, b = 5
清零最低位的 1
- 公式：n & (n - 1)
- 作用：用于统计 1 的个数。
  - 示例：12 (1100) -> n & (n - 1) = 8 (1000)
判断二进制中是否为 2 的幂
- 公式：n > 0 and (n & (n - 1)) == 0
  - 示例：8 (1000) 是 2 的幂；10 (1010) 不是。
位图（Bitmap）算法
- 应用于海量数据处理，用位表示某个值是否存在，大幅节省空间。
  - 示例：检测某个数字是否出现。
位掩码（Bitmask）操作
- 用于权限管理（如读写执行权限），每个位表示一个权限状态。
  - 示例：111 表示 rwx 权限，101 表示 rw-。
图像处理中的像素操作
- 按位与、或操作对图像的颜色、透明度等位级数据进行精细控制。
加法的位运算实现
- 利用异或操作模拟加法：a ^ b（不进位加法）和 a & b（进位）。
哈希函数优化
- 通过位运算快速计算哈希值或减少冲突。
网络编程中的子网掩码

使用按位与确定 IP 地址和子网的关系。

位运算的基础简单但应用广泛，掌握它不仅能提升代码效率，还能帮助开发者深入理解计算机的工作原理。

2. 题目1：位1的个数

题目链接：191. 位1的个数 - 力扣（LeetCode）

题目描述：

2.1 算法思路：

算法核心思想

逐位检查：
- 利用右移（>>）操作，将 n 的最低位逐步移出，然后与 1 按位与（&）操作来检查这一位是否为 1。
- 如果结果是 1，说明当前位是 1，计数器 count 增加 1。
循环 32 次：
- 因为输入是一个 32 位整数（int），需要从最低位到最高位依次检查所有 32 位。
返回计数器：
- 每次遇到 1 时，计数器增加，最终返回这个计数值。

2.2 代码详解

class Solution 
{
public:int hammingWeight(int n) {int count = 0; // 初始化计数器，统计 1 的个数for (int i = 0; i < 32; i++) // 遍历 32 位{if (((n >> i) & 1) == 1) // 右移 i 位后，与 1 按位与，判断最低位是否为 1count++; // 如果是 1，增加计数}return count; // 返回汉明重量}
};

2.2.1 示例分析

输入：n = 11

二进制表示：00000000000000000000000000001011
逐步过程如下：

i = 0: (n >> 0) & 1 = 000...0011 & 1 = 1 -> count = 1
i = 1: (n >> 1) & 1 = 000...001 & 1 = 1 -> count = 2
i = 2: (n >> 2) & 1 = 000...000 & 1 = 0 -> count = 2
i = 3: (n >> 3) & 1 = 000...000 & 1 = 1 -> count = 3
最终结果：count = 3

2.3 时间复杂度与空间复杂度

时间复杂度：
- 循环固定执行 32 次（因为是 32 位整数）。
- 每次循环中执行常数操作：右移和按位与。
- 总时间复杂度为 O(1)，与输入值大小无关。
空间复杂度：
- 只使用了一个额外变量 count，因此是 O(1)。

2.4 改进优化

虽然代码的时间复杂度已经是 O(1)，但在某些场景下可以进一步优化位操作的效率，例如使用 n & (n - 1) 清零最低位的 1。
优化后的代码：

class Solution 
{
public:int hammingWeight(int n) {int count = 0;while (n != 0) // 当 n 不为 0 时，逐位清零最低位的 1{n &= (n - 1); // 清零最低位的 1count++;}return count;}
};

2.4.1 优化思路：

每次操作将当前数字的最低位 1 清零，使得循环次数仅等于 1 的个数。
时间复杂度：O(k)，其中 k 是 1 的个数，适用于输入值中 1 的个数远小于 32 的情况。

2.5 总结

原始方法适合简单直接的逐位统计，适合入门和通用情况。
优化方法更高效，尤其在实际应用中，适用于稀疏数据（1 的个数较少）的场景。

3. 题目2:比特位计数

题目链接：338. 比特位计数 - 力扣（LeetCode）

题目描述：

3.1 算法思路：

辅助函数 hammingWeight 的功能：
- 作用：输入一个整数 n，计算其二进制中 1 的个数。
- 思路：通过循环，逐位检查 n 的每一位是否为 1，如果是，则计数器增加。
- 实现细节：
  - 使用右移运算符 >> 将数字逐位右移。
  - 与 1 进行按位与（&）运算，检查最低位是否为 1。
  - 循环 32 次（针对 32 位整数）。
主函数 countBits 的功能：
- 作用：从 0 到 n，依次调用 hammingWeight 计算每个数字中 1 的个数，并将结果存入数组 arr。
- 思路：
  - 遍历所有数字 i，范围是 [0, n]。
  - 对每个数字 i 调用 hammingWeight，获取其二进制中 1 的个数。
  - 使用 arr.push_back(count) 将结果依次存入数组。
整体流程：
- 初始化数组 arr 用于存储结果。
- 循环从 0 到 n，计算每个数字的 1 个数。
- 返回结果数组 arr。

3.2 示例代码：

// 定义一个辅助函数，用于计算一个整数的二进制中 '1' 的个数
int hammingWeight(int n) 
{int count = 0; // 初始化计数器，用于统计二进制中 '1' 的数量for (int i = 0; i < 32; i++) // 遍历整数的 32 位（假设输入是 32 位整数）{// 右移 i 位，并用按位与操作提取最低位，检查是否为 1if (((n >> i) & 1) == 1) count++; // 如果当前位是 1，计数器加 1}return count; // 返回 '1' 的总个数
}// 定义一个类，包含主函数，用于生成从 0 到 n 每个数字的二进制中 '1' 的个数
class Solution 
{
public:// 主函数，生成结果数组vector<int> countBits(int n) {vector<int> arr; // 定义一个向量用于存储结果，每个元素代表对应数字的二进制中 '1' 的个数int count1 = 0; // 临时变量，用于存储每个数字的 '1' 个数// 遍历从 0 到 n 的每个数字for (int i = 0; i <= n; i++) {count1 = hammingWeight(i); // 调用辅助函数，计算当前数字的 '1' 个数arr.push_back(count1); // 将结果添加到结果数组中}return arr; // 返回结果数组}
};

3.2.1 代码详解

辅助函数 hammingWeight

int hammingWeight(int n) 
{int count = 0;for (int i = 0; i < 32; i++) // 遍历整数的 32 位{if (((n >> i) & 1) == 1) // 检查当前位是否为 1count++; // 如果是，增加计数}return count; // 返回 1 的个数
}

主函数 countBits

class Solution 
{
public:vector<int> countBits(int n) {vector<int> arr; // 用于存储每个数字的汉明重量int count1 = 0;for (int i = 0; i <= n; i++) // 遍历从 0 到 n 的每个数字{count1 = hammingWeight(i); // 计算当前数字的二进制中 1 的个数arr.push_back(count1); // 将结果加入数组}return arr; // 返回结果数组}
};

示例分析

示例输入：n = 5

目标：生成从 0 到 5 的二进制中 1 的个数，即：

0 -> 0000 → 1 的个数 = 0
1 -> 0001 → 1 的个数 = 1
2 -> 0010 → 1 的个数 = 1
3 -> 0011 → 1 的个数 = 2
4 -> 0100 → 1 的个数 = 1
5 -> 0101 → 1 的个数 = 2

输出：[0, 1, 1, 2, 1, 2]

逐步过程：

i = 0 → 调用 hammingWeight(0) → 结果 0 → arr = [0]
i = 1 → 调用 hammingWeight(1) → 结果 1 → arr = [0, 1]
i = 2 → 调用 hammingWeight(2) → 结果 1 → arr = [0, 1, 1]
i = 3 → 调用 hammingWeight(3) → 结果 2 → arr = [0, 1, 1, 2]
i = 4 → 调用 hammingWeight(4) → 结果 1 → arr = [0, 1, 1, 2, 1]
i = 5 → 调用 hammingWeight(5) → 结果 2 → arr = [0, 1, 1, 2, 1, 2]

最终返回 arr = [0, 1, 1, 2, 1, 2]。

3.3 时间复杂度与空间复杂度

时间复杂度：

主函数：从 0 到 n 遍历了 n + 1 个数字。
辅助函数：每次调用 hammingWeight 执行了 32 次操作（检查 32 位）。
总体复杂度：O(n * 32)，即 O(32n)，等价于 O(n)。

空间复杂度：

存储结果数组 arr，大小为 n + 1。
总空间复杂度为 O(n)。

3.4 优化思路

当前实现中，每次计算每个数字的汉明重量时，完全独立地逐位检查。可以通过 动态规划 优化，利用前一个数字的结果推导当前数字的汉明重量。优化方法为：

观察规律：
- 如果 i 是偶数，则 countBits(i) = countBits(i / 2)（右移一位，相当于去掉最低位）。
- 如果 i 是奇数，则 countBits(i) = countBits(i / 2) + 1（最低位为 1）。
动态规划实现：

class Solution 
{
public:vector<int> countBits(int n) {vector<int> dp(n + 1, 0); // 初始化结果数组，dp[i] 表示数字 i 的汉明重量for (int i = 1; i <= n; i++) {dp[i] = dp[i >> 1] + (i & 1); // 动态转移方程}return dp;}
};

优化复杂度：时间复杂度降为 O(n)，空间复杂度仍为 O(n)。

3.5 总结

初始实现通过逐位计算每个数字的汉明重量，简单直观，时间复杂度为 O(n * 32)。
动态规划优化利用子问题结果，减少重复计算，时间复杂度降为 O(n)。

4. 题目3：汉明距离

题目链接：461. 汉明距离 - 力扣（LeetCode）

题目描述：

4.1 算法思路：

算法分为两部分

辅助函数 hammingWeight：
- 计算一个整数的二进制表示中 1 的个数（即汉明重量，Hamming Weight）。
- 通过逐位右移（>>）和按位与（&）操作，统计 1 的个数。
主函数 hammingDistance：
- 计算两个整数 x 和 y 的汉明距离。
- 使用按位异或（^）操作找出 x 和 y 的二进制表示中不同的位，结果是一个新整数 s。
- 调用 hammingWeight 函数统计 s 中的 1 的个数，即为汉明距离。

4.2 示例代码：

// 辅助函数：计算整数 n 的二进制表示中 '1' 的个数
int hammingWeight(int n) 
{int count = 0; // 初始化计数器，用于统计二进制中 '1' 的数量for (int i = 0; i < 32; i++) // 遍历 32 位（假设输入为 32 位整数）{// 右移 i 位，并与 1 进行按位与操作，检查最低位是否为 1if (((n >> i) & 1) == 1) count++; // 如果最低位为 1，则计数器加 1}return count; // 返回二进制中 '1' 的总数
}// 主类：用于计算两个整数的汉明距离
class Solution 
{
public:// 主函数：计算 x 和 y 的汉明距离int hammingDistance(int x, int y) {// 按位异或操作，得到二进制中 x 和 y 不同的位// 异或规则：相同位结果为 0，不同位结果为 1int s = x ^ y;// 调用辅助函数 hammingWeight，统计异或结果中 '1' 的个数// 这些 '1' 的数量即为 x 和 y 的汉明距离return hammingWeight(s);}
};

4.2.1 代码逻辑详细解析

辅助函数 hammingWeight：
- 功能：统计整数 n 的二进制表示中 1 的个数。
- 方法：通过逐位右移操作，依次提取最低位并判断是否为 1。
  - n >> i：将整数 n 右移 i 位。
  - (n >> i) & 1：提取右移后结果的最低位，并判断是否为 1。
- 时间复杂度：固定遍历 32 位，时间复杂度为 O(32)，即 O(1)。
主函数 hammingDistance：
- 功能：计算两个整数 x 和 y 的汉明距离。
- 方法：
  - 通过按位异或（x ^ y）操作，生成一个新的整数 s，其二进制表示中 1 的位置对应 x 和 y 不同的位。
    - 异或规则：
      
      1 ^ 1 = 0 0 ^ 0 = 0 1 ^ 0 = 1 0 ^ 1 = 1
    - 因此，s 的二进制中所有的 1 表示 x 和 y 不同的位。
  - 调用 hammingWeight 函数，统计 s 中 1 的个数，作为 x 和 y 的汉明距离。
- 时间复杂度：
  - 异或操作时间复杂度为 O(1)。
  - 调用 hammingWeight 时间复杂度为 O(32)，即 O(1)。

示例运行过程

示例输入

x = 1, y = 4

计算过程

x 的二进制表示：0001
y 的二进制表示：0100
按位异或：

x ^ y = 0001 ^ 0100 = 0101

异或结果为：0101。
调用 hammingWeight(5)：
- 5 的二进制表示为：0101。
- 遍历每一位：
  - 第 0 位：1 → count = 1
  - 第 1 位：0 → count = 1
  - 第 2 位：1 → count = 2
  - 第 3 位：0 → count = 2
- 返回 count = 2。
最终返回汉明距离：2

输出

2

4.3 时间复杂度和空间复杂度

时间复杂度

异或操作：按位异或操作的时间复杂度为 O(1)。
辅助函数 hammingWeight：遍历 32 位，时间复杂度为 O(1)。
总时间复杂度：O(1)。

空间复杂度

使用常量级的变量（如 count 和 s），不需要额外空间，O(1)。

4.4 代码特点

优点：
- 简单直观，通过辅助函数分离逻辑，代码结构清晰。
- 时间复杂度和空间复杂度均为常量级，性能优良。
可优化方向：
- 优化 hammingWeight 函数，利用 n & (n - 1) 方法快速清除最低位的 1，减少迭代次数

优化后的辅助函数

int hammingWeight(int n) 
{int count = 0;while (n != 0) // 当 n 不为 0 时{n &= (n - 1); // 清除最低位的 1count++; // 每次清除后计数加 1}return count; // 返回二进制中 '1' 的总数
}

优势：循环次数等于 1 的个数，适用于二进制中 1 较少的情况，进一步提升性能。

完整优化代码

int hammingWeight(int n) 
{int count = 0;while (n != 0) {n &= (n - 1);count++;}return count;
}class Solution 
{
public:int hammingDistance(int x, int y) {int s = x ^ y; // 按位异或，找出 x 和 y 不同的位return hammingWeight(s); // 统计不同位的数量（即 '1' 的个数）}
};

5. 题目4：只出现1的次数

题目链接：136. 只出现一次的数字 - 力扣（LeetCode）

题目描述：

5.1 算法思路

异或运算的特性：
- 异或（^）运算的规则：
  - a ^ a = 0（任何数与自己异或，结果为 0）
  - a ^ 0 = a（任何数与 0 异或，结果不变）
  - 异或满足交换律和结合律：a ^ b ^ c = a ^ c ^ b。
- 因此，如果一个数出现两次，它们会相互抵消为 0。
- 只出现一次的数与 0 异或后仍是其本身。
核心逻辑：
- 遍历数组中的每个元素，对每个元素执行 异或操作。
- 最终，所有出现两次的数字会抵消为 0，只剩下那个出现一次的数字。

5.2 示例代码：

class Solution 
{
public:int singleNumber(vector<int>& nums) {int ret = 0; // 初始化结果为 0for (auto s : nums) // 遍历数组中的每个元素{ret ^= s; // 异或操作：逐个元素与结果异或}return ret; // 返回出现一次的数字}
};

5.2.1 执行过程示例

输入示例

nums = [4, 1, 2, 1, 2]

执行过程

最终结果：4

5.3 时间复杂度与空间复杂度

时间复杂度：
- 遍历整个数组一次，每个元素进行一次异或操作。
- 时间复杂度为 O(n)，其中 n 是数组的长度。
空间复杂度：
- 使用了一个整数 ret 进行累加异或，不需要额外的数据结构。
- 空间复杂度为 O(1)。

5.4 多种解法

5.4.1 解法二：哈希表法

思路

使用 哈希表 记录每个元素出现的次数。
遍历哈希表，找到次数为1的元素。

代码实现

class Solution {
public:int singleNumber(vector<int>& nums) {unordered_map<int, int> countMap;for (int num : nums) {countMap[num]++; // 记录每个元素出现的次数}for (auto& pair : countMap) {if (pair.second == 1) { // 找到只出现一次的元素return pair.first;}}return -1; // 兜底返回}
};

时间复杂度：O(n) — 遍历数组和哈希表

空间复杂度：O(n) — 额外使用哈希表存储元素及其频次

5.4.2 解法三：排序法

思路

对数组进行排序，相同的元素会相邻。
遍历排序后的数组，如果某个元素与前一个和后一个元素不同，它就是只出现一次的数。

代码实现

class Solution {
public:int singleNumber(vector<int>& nums) {sort(nums.begin(), nums.end()); // 排序数组for (int i = 0; i < nums.size(); i += 2) { // 每次跳两个位置if (i == nums.size() - 1 || nums[i] != nums[i + 1]) { return nums[i]; // 如果元素和下一个元素不同，返回该元素}}return -1; // 兜底返回}
};

时间复杂度：O(n log n) — 排序的时间复杂度

空间复杂度：O(1) — 如果排序算法为原地排序

5.4.3 解法四：数学法（2∗sum - sum）

思路

利用集合（Set）去重后计算数组中元素的和。
原始数组中所有元素之和减去去重后的和的两倍，结果就是只出现一次的数。

代码实现

class Solution {
public:int singleNumber(vector<int>& nums) {unordered_set<int> numSet;int sumOfNums = 0, sumOfSet = 0;for (int num : nums) {sumOfNums += num; // 数组中所有元素的和if (numSet.find(num) == numSet.end()) { // 如果元素不在集合中numSet.insert(num);sumOfSet += num; // 记录集合中元素的和}}return 2 * sumOfSet - sumOfNums; // 根据公式计算结果}
};

时间复杂度：O(n) — 遍历数组

空间复杂度：O(n) — 额外使用集合

5.4.4 解法对比总结

5.5 总结

关键点：利用异或的特性，重复出现的数字会被抵消（a ^ a = 0），最终只剩下不重复的那个数。
优势：
- 时间复杂度为 O(n)，一次遍历解决问题。
- 空间复杂度为 O(1)，无需额外存储空间。
适用场景：数组中有且只有一个数字出现一次，其余数字均出现两次

6. 题目5：只出现一次的数字 |||

题目链接：260. 只出现一次的数字 III - 力扣（LeetCode）

题目描述：

6.1 算法思路：

思路解析

步骤1：使用异或找出两个数字的异或结果

将数组中所有数字进行异或，最终结果 xorsum 是这两个不同数字的异或结果。
- 原因：
  - 相同的数字异或为 0（a ^ a = 0）。
  - 0 与任何数异或不改变数值（a ^ 0 = a）。
  - 因此，数组中成对的数字会相互抵消，只剩下两个不同的数字的异或结果。
- xorsum 的特点：
  - 它是两个只出现一次的数字的 异或值，即 xorsum = num1 ^ num2，其中 num1 和 num2 是结果。

步骤2：找到异或结果中最低的不同位（区分两组数字）

异或结果 xorsum 中的 最低位的1，表示在这一位上，两个不同数字的二进制表示不同（一个是 1，另一个是 0）。
- 通过 xorsum & (-xorsum) 找出最低的1位：
  - (-xorsum) 是 xorsum 的补码，补码中保留最低位的1并将其他位取反。
  - xorsum & (-xorsum) 可以快速找到最低位的1。
这位 lsb（lowest significant bit）可以将数组中的所有数字分为两组：
- 第一组：在该位上为 1 的数字。
- 第二组：在该位上为 0 的数字。

步骤3：分别异或两组数字，得到两个结果

将数组中的所有数字根据最低位的1进行分组。
对每一组的数字分别进行异或：
- 在第一组中，所有成对的数字（出现两次的数字）会互相抵消，最终结果是 num1。
- 在第二组中，所有成对的数字也会互相抵消，最终结果是 num2。

6.2 代码解析

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {int xorsum = 0; // 用于存储所有数字的异或结果for (int num: nums) {xorsum ^= num; // 所有数字异或，最终结果是两个不同数字的异或值}// 找出 xorsum 中最低位的 1（用于区分两个数字）// 如果 xorsum 是 INT_MIN（最小负数），它本身只有最高位为 1，不会溢出int lsb = (xorsum == INT_MIN ? xorsum : xorsum & (-xorsum));int type1 = 0, type2 = 0; // 用于存储两个只出现一次的数字for (int num: nums) {if (num & lsb) { // 根据最低位的1分组：该位为1type1 ^= num; // 第一组异或，得到 num1}else { // 该位为0type2 ^= num; // 第二组异或，得到 num2}}return {type1, type2}; // 返回结果}
};

6.2.1 示例执行过程

输入

nums = [1, 2, 1, 3, 2, 5]

步骤1：计算所有元素的异或结果

1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5 = 3 ^ 5 = 6（二进制 0110）
6 是 3 和 5 的异或结果。

步骤2：找到最低位的1

xorsum = 6 → 二进制 0110
xorsum & (-xorsum) = 2（最低位的1在第2位）。

步骤3：根据最低位的1分组

分组1（第2位为1的数字）：2, 2, 3
分组2（第2位为0的数字）：1, 1, 5

步骤4：分别异或两组

第一组：2 ^ 2 ^ 3 = 3
第二组：1 ^ 1 ^ 5 = 5

输出

[3, 5]（结果顺序不唯一）。

6.3 复杂度分析

时间复杂度分析

第一次遍历：计算所有数字的异或，时间复杂度为 O(n)。
第二次遍历：根据最低位的1分组并分别异或，时间复杂度为 O(n)。
总体时间复杂度：O(n)。

空间复杂度分析

使用了常数额外空间，空间复杂度为 O(1)。

6.4 多种解法思路

6.4.1 解法二：哈希表法

思路

使用哈希表记录每个元素的出现次数。
遍历哈希表，找到出现次数为1的两个元素。

代码实现

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {unordered_map<int, int> freq; // 统计元素出现的频率for (int num : nums) {freq[num]++;}vector<int> result;for (auto& pair : freq) {if (pair.second == 1) { // 出现次数为1的元素result.push_back(pair.first);}}return result;}
};

复杂度分析

时间复杂度：O(n)，一次遍历数组和哈希表。
空间复杂度：O(n)，额外的哈希表空间。

6.4.2 解法三：排序法

思路

对数组进行排序，相同的元素会相邻。
遍历排序后的数组，如果某个元素与前后元素都不相同，则它是目标元素之一。

代码实现

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {sort(nums.begin(), nums.end()); // 排序数组vector<int> result;for (int i = 0; i < nums.size(); i++) {if ((i == 0 || nums[i] != nums[i - 1]) && (i == nums.size() - 1 || nums[i] != nums[i + 1])) {result.push_back(nums[i]);}}return result;}
};

复杂度分析

时间复杂度：O(n log n)，排序的时间复杂度。
空间复杂度：O(1)，原地排序（如果排序算法是原地的）

6.4.3 解法对比总结

6.5 总结

异或法是解决此类问题的核心思想，利用异或的性质实现高效解法。
通过 最低位的1 将两个不同的数字区分开来，巧妙地将问题分解为两组。
该解法时间复杂度为 O(n)，空间复杂度为 O(1)，性能最优。

7. 总结要点

异或运算 是位运算解决重复出现问题的核心思想：
- 相同为0，0与任何数异或等于数本身。
位统计 + 取模：通过逐位统计 1 的个数，可以解决 K次出现问题。
低位的1：通过提取最低位的1，可以将数字分组，解决两个目标数字的问题。

8. 最后

通过上面几个例题：「Single Number」的异或运算解法、「Single Number III」的异或+分组方法，以及**「Single Number II」的位统计与取模优化**，我们总结出位运算在数组问题中的高效应用。

位运算 通过将复杂的数字出现次数、分组、去重等问题转化为简单的位级操作（如异或、位统计、取模等），极大地提升了问题求解的效率。
在处理 元素重复出现问题、分组求解问题 以及 高效数值处理 等场景时，位运算展现出显著的性能优势，尤其适用于 大规模数据 和 时间复杂度敏感 的应用场景。

路虽远，行则将至；事虽难，做则必成

亲爱的读者们，下一篇文章再会！！！

中国的网络营销公司_建筑设计公司名称起名_台州seo排名扣费_日本搜索引擎

文章目录

1. C++ 位运算算法 详解

1.1 位运算的重要性

1.2 位运算的定义

1.3 位运算的核心思想

1.4 经典应用

2. 题目1：位1的个数

2.1 算法思路：

2.2 代码详解

2.2.1 示例分析

2.3 时间复杂度与空间复杂度

2.4 改进优化

2.4.1 优化思路：

2.5 总结

3. 题目2:比特位计数

3.1 算法思路：

3.2 示例代码：

3.2.1 代码详解

3.3 时间复杂度与空间复杂度

3.4 优化思路

3.5 总结

4. 题目3：汉明距离

4.1 算法思路：

4.2 示例代码：

4.2.1 代码逻辑详细解析

4.3 时间复杂度和空间复杂度

4.4 代码特点

5. 题目4：只出现1的次数

5.1 算法思路

5.2 示例代码：

5.2.1 执行过程示例

5.3 时间复杂度与空间复杂度

5.4 多种解法

5.4.1 解法二：哈希表法

5.4.2 解法三：排序法

5.4.3 解法四：数学法（2∗sum - sum）

5.4.4 解法对比总结

5.5 总结

6. 题目5：只出现一次的数字 |||

6.1 算法思路：

6.2 代码解析

6.2.1 示例执行过程

6.3 复杂度分析

6.4 多种解法思路

6.4.1 解法二：哈希表法

6.4.2 解法三：排序法

6.4.3 解法对比总结

6.5 总结

7. 总结要点

8. 最后

最新新闻

热搜词

1. C++ 位运算算法详解