刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

面试题

请描述一下在给定数组中找出两个数字,这两个数字只出现一次,其他数字都出现多次,你会采取什么样的算法或策略来找出这两个数字?

使用微信搜索喵呜刷题,轻松应对面试!

答案:

解答思路:

这个问题可以通过异或操作来解决。异或操作有一个特性,即任何数与自身异或的结果为0,任何数与0异或的结果为它本身。我们可以遍历数组,利用异或操作找出出现两次的数字和只出现一次的数字。假设数组中除了两个数字只出现一次外,其余数字都出现两次或以上,那么将数组中所有数字进行异或操作的结果即为这两个只出现一次的数字异或的结果。然后我们可以利用位运算的性质进一步找出这两个数字。

最优回答:

首先,将所有数字进行异或操作得到结果xorResult。然后观察xorResult的二进制表示,找到为1的某一位,根据这一位将数组分成两个子集。由于这两个只出现一次的数字在这一位上必然一个为0,一个为1,所以这两个数字会分别落在上述两个子集中。然后分别对这两个子集进行异或操作,得到的结果即为这两个只出现一次的数字。

解析:

  1. 异或操作:二进制异或操作,符号为^,规则为相同得0,不同得1。例如,5的二进制表示为101,7的二进制表示为111,那么5^7的结果为100(即十进制中的4)。异或操作的一个重要特性是任何数与自身异或的结果为0,任何数与0异或的结果为它本身。
  2. 位运算:在计算机科学中,位运算是指直接对整数的二进制位进行的操作。常见的位运算有移位操作(左移«、右移»)、位与&、位或|和异或^等。这些操作在计算机内部实现高效的数据处理和信息提取。
  3. 数字的二进制表示:在计算机中,所有的信息都是以二进制的形式存储和处理的。数字也需转化为二进制形式进行位运算等操作。了解数字的二进制表示有助于理解和运用位运算等知识解决实际问题。
创作类型:
原创

本文链接:请描述一下在给定数组中找出两个数字,这两个数字只出现一次,其他数字都出现多次,你会采取什么样的算法或

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share