本文共 669 字,大约阅读时间需要 2 分钟。
一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。示例 1:输入:nums = [4,1,4,6]输出:[1,6] 或 [6,1]示例 2:输入:nums = [1,2,10,4,1,4,3,3]输出:[2,10] 或 [10,2] 限制:2 <= nums <= 10000来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
方法1
1、使用hashmap或者hashset存储,只需遍历一遍即可得出正确答案
但题目要求空间复杂度为o(1),不符合要求
方法2
1、使用异或^,将所有元素异或一遍,结果的某一位肯定不为0
2、使用&判断出具体哪一位不为0,例如第三位,则tmp=0010 3、然后遍历数组,将每一位数字和tmp进行&操作,如果为0则分为a组,否则为b组 4,将a组中的元素进行异或就得到结果1,将b组中的元素进行异或得到结果2
class Solution { public int[] singleNumbers(int[] nums) { int[] res= new int[2]; int flag=0; for(int i=0;i