题解 | #只出现一次的牛II#

只出现一次的牛II

https://www.nowcoder.com/practice/fde24d7d8f97467e91403d255243ee1c

思路

经典题

异或有如下特性

a ^ a = 0,

a != b 必然 a ^ b != 0

根据该特性,把整个数组进行异或和s,必然为非0,而这个非0,必然是由两个孤立的值提供

然后根据s,其中的某一个幂次不为0,进行分组

然后在进行分组求异或和

为啥要这么做呢?

如果一组只有一个孤立值,那异或和必然为孤立值本身

这边通过分组,巧妙地把两个孤立数,分在两个不同的组中。

最后的结果,比对大小,那个小,放在前面。

代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型一维数组
     */
    public int[] findSingleCowsII (int[] nums) {
        int xor = 0;
        for (int v: nums) {
            xor ^= v;
        }
       // 返回非0的某个幂次
        int pos = Integer.lowestOneBit(xor);

        int v1 = 0, v2 = 0;
        for (int v: nums) {
            // 进行分组
            if ((pos & v) != 0) v1 ^= v;
            else v2 ^= v;
        }
  
        if (v1 > v2) return new int[] {v2, v1};
        else return new int[] {v1, v2};
    }

}

全部评论

相关推荐

牛客769922382号:轮到大佬给公司发感谢信了,想想就爽
点赞 评论 收藏
分享
今年会有offer吗:一眼代码相似度过高
投递华为等公司10个岗位
点赞 评论 收藏
分享
2 1 评论
分享
牛客网
牛客企业服务