找出数组中只出现一次的数字

举报
游离 发表于 2023/02/02 20:20:37 2023/02/02
【摘要】 一个数组中,有一个数字只出现一次,其余的数都出现两次,求出那个单独的数可以使用异或或来解决这个问题,因为两个相同的数异或之后就是0,0与一个数异或还是这个数,而且异或满足交换律public static void main(String[] args) { int[] arr = {1, 2, 3, 2, 1}; int n=0; for (int ...

一个数组中,有一个数字只出现一次,其余的数都出现两次,求出那个单独的数

可以使用异或或来解决这个问题,因为两个相同的数异或之后就是0,0与一个数异或还是这个数,而且异或满足交换律

public static void main(String[] args) {
        int[] arr = {1, 2, 3, 2, 1};
        int n=0;
        for (int i = 0; i < arr.length; i++) {
            n ^= arr[i];//与sun+=arr[i]类似,方便理解
        }
        System.out.println(n);
    }
复制代码

拓展:

一个数组中,只有两个不同的数字出现一次,其余的数都出现两次,求出那两个只出现一次的数

思路:假设数组是{1,2,3,1},要想找到那两个只出现一次的数,只需要将数组里面所有的数字异或一下,得到结果sum,然后将sum进行移位操作判断是否为1,如果不为1,依次往后,知道右移到位为1的时候为止,其实就是确定sum从右往左数第几位是1,从而起到筛选的作用,

接下来将数组遍历一遍,判断数组中的每个数是否满足移k位结果是否为1,(((sum >> k) & 1)是常见的判断位数上是1还是0的方法),如果是1,就将其全部异或起来,这样就可以找到num1

当找到num1时,num2=sum^num1,因为sum=num1 ^num2,所以在异或一个num1就可以得到num2

总结:简单来说,就是通过移位操作来达到分类的作用,接下来就是使用之前异或的方法即可

代码如下

public static int[] Search(int[] arr) {
        int sum = 0;
        int num1 = 0;
        int num2 = 0;
        int k = 0;
        for (int i = 0; i < arr.length; i++) {
            sum ^= arr[i];
        }
        while (((sum >> k) & 1) != 1) {
            k++;
        }
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] >> k & 1) == 1) {
                num1 ^= arr[i];
            }
        }
        num2 = sum ^ num1;
        return new int[]{num1, num2};
    }

    public static void main(String[] args) {
        int[] arr = {6, 3, 2, 4, 3, 6};
        System.out.println(Arrays.toString(Search(arr)));
    }

复制代码

欢迎点赞收藏关注,感谢大家的支持!

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。