剑指offer56-Ⅰ 数组中数字出现的次数【数学】
题目描述
一个整型数组 nums
里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是**O(n),空间复杂度是O(1)**。
示例 1:
1 | 输入:nums = [4,1,4,6] |
示例 2:
1 | 输入:nums = [1,2,10,4,1,4,3,3] |
限制:
2 <= nums.length <= 10000
解题思路
方法一:数学-异或
先遍历一遍数组,用0异或所有数,得出结果为t,则t为答案值a,b的异或结果,则将cp=1,进行处理,得到a,b两个数不同的最小位。
再一次遍历数组,如果数与cp的和&值为0,则被分为a,不为0,被分为b.
则结果a为a类所有数的异或值。
代码实现
1 | class Solution { |
复杂度分析
时间复杂度:O(n)
空间复杂度:O(1)
资料
剑指offer56-Ⅰ 数组中数字出现的次数【数学】
You need to set
install_url
to use ShareThis. Please set it in _config.yml
.