【leetcode79】Single Number III

我不是女神ヾ 2022-09-24 12:28 142阅读 0赞

# 题目描述： #

## 给定一个数组，里面只有两个数组，只是出现一次，其余的数字都是出现两次，找出这个两个数字，数组形式输出 ##

# 原文描述： #

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

## For example: ##

Given nums = \[1, 2, 1, 3, 2, 5\], return \[3, 5\].

## Note: ##

The order of the result is not important. So in the above example, \[5, 3\] is also correct.  
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

# 思路： #

*  考虑使用位运算  
    \-那数组分为两组，每个组只有一个出现一次的数字，单独进行异或处理，考虑用全部异或的方式
 *  假设得到异或的结果是A，由于两个数字不同。A肯定有一个位是1，找到那个位，然后用来把这个数组分为两组
 *  其中一个组的异或结果是B，输出【B，A ^ B】

# 代码： #

public class Solution {
        public int[] singleNumber(int[] nums) {
            int xOne = 0;
            for (int x : nums) {
                xOne ^= x;
            }
    
            // 获取第一个位1的索引
            int k = 0;
            for (k = 0; k < Integer.SIZE; ++ k) {
                if (((xOne >>> k) & 1) == 1) {
                    break;
                }
            }
    
            int xTwo = 0;
            for (int x : nums) {
                if (((x >>> k) & 1) == 1) {
                    xTwo ^= x;
                }
            }
            return new int[] {xTwo, xOne ^ xTwo};
        }
    }

# 更多的leetcode的经典算法，查看我的leetcode专栏，链接如下： #

[leetcode专栏][leetcode]

[leetcode]: http://blog.csdn.net/column/details/fengsheng.html