使用位操作高效解决单个元素出现问题【位运算】

2024-09-03 19:44

本文主要是介绍使用位操作高效解决单个元素出现问题【位运算】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

使用位操作高效解决单个元素出现问题

在日常的算法面试和编程挑战中,常常会遇到寻找单个出现元素的问题。尽管可以用哈希表(map)轻松解决,但要求更高效的线性时间复杂度和常量空间复杂度时,位操作特别是异或(XOR)运算提供了一个巧妙的解决方案。本篇博客将深入探讨这个问题,详细解释异或运算的特性,并展示其在解决该类问题中的强大作用。

问题描述:

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找到那个只出现了一次的元素。

示例:

  • 输入: nums = [4,1,2,1,2]
  • 输出: 4

136. 只出现一次的数字 - 力扣(LeetCode)

常规解法:使用 map 记录次数

最初,我们可能会想到使用一个哈希表来记录每个元素的出现次数,然后遍历哈希表找到那个只出现一次的元素。具体步骤如下:

  1. 创建一个哈希表,遍历数组并记录每个元素的出现次数。
  2. 再次遍历哈希表,找到只出现一次的元素并返回。

这种方法虽然直观且易于理解,但由于需要额外的存储空间来保存元素的出现次数,空间复杂度为 (O(n))。

代码实现:

#include <iostream>
#include <vector>
#include <unordered_map>using namespace std;class Solution {
public:int singleNumber(vector<int>& nums) {unordered_map<int, int> countMap;for (int num : nums) {countMap[num]++;}for (auto& entry : countMap) {if (entry.second == 1) {return entry.first;}}return -1;  // Ideally, this line should never be reached.}
};int main() {Solution sol;vector<int> nums = {4, 1, 2, 1, 2};cout << "The single number is: " << sol.singleNumber(nums) << endl;return 0;
}

分析:

  • 时间复杂度:由于我们遍历了数组两次,因此时间复杂度为 (O(n))。
  • 空间复杂度:需要 (O(n)) 的额外空间来存储哈希表。

尽管这种方法解决了问题,但它不符合题目要求的常量空间复杂度。为此,我们需要寻找更高效的解决方案。

高效解法:使用异或运算

异或运算的性质:

  • 交换律a ^ b = b ^ a
  • 结合律a ^ (b ^ c) = (a ^ b) ^ c
  • 任何数与0异或等于它本身a ^ 0 = a
  • 任何数与自己异或等于0a ^ a = 0

基于这些性质,我们可以推导出一个重要结论:如果对数组中所有的元素进行异或运算,那么出现两次的元素都会相互抵消,最终的结果就是那个只出现了一次的元素

具体步骤:
  1. 初始化一个变量 res 为0。
  2. 遍历整个数组,将每个元素与 res 进行异或运算。
  3. 遍历结束后,res 中存储的就是那个只出现了一次的元素。
代码实现:
#include <iostream>
#include <vector>using namespace std;class Solution {
public:int singleNumber(vector<int>& nums) {int res = 0;for (int num : nums) {res ^= num;  // 进行异或运算}return res;}
};int main() {Solution sol;vector<int> nums = {4, 1, 2, 1, 2};cout << "The single number is: " << sol.singleNumber(nums) << endl;return 0;
}

详细解释:

  • nums = [4, 1, 2, 1, 2],初始 res = 0
  • 遍历数组并依次异或每个元素:
    • res = 0 ^ 4 = 4
    0000
^ 0100
_______0100
  • res = 4 ^ 1 = 5
   0100
^ 0001
_______0101
  • res = 5 ^ 2 = 7
   0101
^ 0010
_______0111
  • res = 7 ^ 1 = 6
   0111
^ 0001
_______0110
  • res = 6 ^ 2 = 4
   0110
^ 0010
_______0100
  • 最终结果 res = 4,即那个只出现了一次的元素。
性能分析:

时间复杂度:
由于我们只遍历了一次数组,所以时间复杂度为 (O(n)),与使用哈希表的方法相同。

空间复杂度:
我们只使用了一个额外的变量 res,所以空间复杂度为 (O(1)),这比哈希表的方法更优。

异或运算在其他场景中的应用:

异或运算不仅在寻找单个出现元素的问题中有应用,还可以用于以下场景:

1. 交换两个变量的值

在C++或其他支持按位运算的语言中,可以使用异或运算来在没有额外存储空间的情况下交换两个变量的值。这是因为对于任何数字 ab,有以下性质:

  • a ^ b ^ b = a (两次异或同一个数等于原数)
  • a ^ a = 0 (任何数与自己异或等于0)

基于这两个性质,可以编写如下代码来交换两个变量 ab

void swapWithoutTemp(int &a, int &b) {a = a ^ b;  // a现在存储的是a^bb = a ^ b;  // b现在存储的是a (因为a^b^b=a)a = a ^ b;  // a现在存储的是b (因为a^b^a=b)
}

2. 检测两个数的不同位

异或运算可以帮助我们找到两个整数之间不同的二进制位。如果两个位相同,则异或结果为0;如果不同,则结果为1。因此,通过异或运算,我们可以很容易地找出两个数的二进制表示中哪些位不同。

bool bitsDiffer(int a, int b) {int diff = a ^ b;while (diff != 0) {if (diff & 1) {// 当前位不同std::cout << "Bit differs at position: " << 31 - __builtin_clz(diff) << std::endl;}diff >>= 1;}
}

这里使用了__builtin_clz函数来找到最高位1的位置,并计算出具体哪一位不同。__builtin_clz返回的是从左边开始第一个非零位的位置,所以需要减去这个值以得到具体的位位置。

3. 求两个数的汉明距离

汉明距离是指两个字符串或数字的二进制表示中对应位不同的数量。使用异或运算,然后计算结果中1的个数,就可以得到汉明距离。

int hammingDistance(int x, int y) {int xorResult = x ^ y;int distance = 0;while (xorResult) {distance += xorResult & 1; // 如果最低位为1,则增加距离xorResult >>= 1; // 移除最低位}return distance;
}

这段代码首先计算出xy之间的异或结果,然后通过逐位检查并计数结果中的1来得出汉明距离。这种方法适用于任何整数类型。

总结:

在处理数组中找出唯一的单个出现元素的问题时,异或运算提供了一个高效且优雅的解决方案。相比于使用哈希表记录次数的方法,异或运算不仅能保证线性时间复杂度,还能将空间复杂度降至常量。

通过理解和掌握异或运算的性质,我们不仅能更好地解决这一类问题,还能将其应用到其他相关的算法场景中,大大提升算法编写的效率和性能。

这篇关于使用位操作高效解决单个元素出现问题【位运算】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1133865

相关文章

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

Pandas使用AdaBoost进行分类的实现

《Pandas使用AdaBoost进行分类的实现》Pandas和AdaBoost分类算法,可以高效地进行数据预处理和分类任务,本文主要介绍了Pandas使用AdaBoost进行分类的实现,具有一定的参... 目录什么是 AdaBoost?使用 AdaBoost 的步骤安装必要的库步骤一:数据准备步骤二:模型

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

使用Pandas进行均值填充的实现

《使用Pandas进行均值填充的实现》缺失数据(NaN值)是一个常见的问题,我们可以通过多种方法来处理缺失数据,其中一种常用的方法是均值填充,本文主要介绍了使用Pandas进行均值填充的实现,感兴趣的... 目录什么是均值填充?为什么选择均值填充?均值填充的步骤实际代码示例总结在数据分析和处理过程中,缺失数

C语言中位操作的实际应用举例

《C语言中位操作的实际应用举例》:本文主要介绍C语言中位操作的实际应用,总结了位操作的使用场景,并指出了需要注意的问题,如可读性、平台依赖性和溢出风险,文中通过代码介绍的非常详细,需要的朋友可以参... 目录1. 嵌入式系统与硬件寄存器操作2. 网络协议解析3. 图像处理与颜色编码4. 高效处理布尔标志集合

如何使用 Python 读取 Excel 数据

《如何使用Python读取Excel数据》:本文主要介绍使用Python读取Excel数据的详细教程,通过pandas和openpyxl,你可以轻松读取Excel文件,并进行各种数据处理操... 目录使用 python 读取 Excel 数据的详细教程1. 安装必要的依赖2. 读取 Excel 文件3. 读

关于MongoDB图片URL存储异常问题以及解决

《关于MongoDB图片URL存储异常问题以及解决》:本文主要介绍关于MongoDB图片URL存储异常问题以及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录MongoDB图片URL存储异常问题项目场景问题描述原因分析解决方案预防措施js总结MongoDB图

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

MySQL重复数据处理的七种高效方法

《MySQL重复数据处理的七种高效方法》你是不是也曾遇到过这样的烦恼:明明系统测试时一切正常,上线后却频频出现重复数据,大批量导数据时,总有那么几条不听话的记录导致整个事务莫名回滚,今天,我就跟大家分... 目录1. 重复数据插入问题分析1.1 问题本质1.2 常见场景图2. 基础解决方案:使用异常捕获3.