首页 > 编程学习 > 每日一练Day04:寻找单身狗

每日一练Day04:寻找单身狗

发布时间:2022/11/8 15:33:56

寻找单身狗

  • 一、一个单身狗
  • 二、两个单身狗


寻找单身狗实际上是力扣上的《只出现一次的数字》具体描述如下:

一、一个单身狗

本题的特点是: 非空数组、其余数字出现两次、寻找只出现一次的数字。那么如何寻找那个”单身狗“呢?

思路:
我们已学过异或操作符^,异或的特点是,对应二进制位相同为0,相异为1。了解这样的原理就可以很容易得到,如果对应两个相同的数字,异或结果必为0,0和非零数字异或为非零数字。已知这种原理后,如果我们将数组中的所有元素异或,出现两次的的元素将异或为0,0与“单身狗”异或恰能得到所求“单身狗”。

理论成立,实践开始:

    public static int singleNumber(int[] array) {
        int num=0;
        for (int i = 0; i < array.length ; i++) {
            num^=array[i];
        }
        return num;
    }

测试结果:


二、两个单身狗

本题可以说是上一题的进阶版本,难度也由简单——>中等。

题目特点: 非空数组、其余数字都出现了两次、寻找两个只出现一次的数字。

思路:
对于这道题如果我们还是将所有元素异或,显然是得不到答案的。那么应该怎么做呢?解决这道问题用到了数字的分组,如果我们将存在的两个“单身狗“分别分到不同的两组中,剩下的两两相同的数字分别分到两边,依旧是异或的原理,将两组数字分别异或,最后得到的两个异或结果不就是最终答案吗?

当然,说的简单,我们该怎样分组呢?这里提供了这样一种思路:

1、首先我们先将所以的数字异或,由于仅有两个“单身狗”,其余数字均出现两次,这样得到的结果就相当于是两个”单身狗“异或的结果。

2、由于我们的目的很明确,就是将两个”单身狗“分别分到两个组中,其余两两相同的数字放到它们两边即可。所以我们可以找到异或后二进制为1的位,因为二进制为1说明这是两个”单身狗“数字不同的二进制位,以此二进制位进行分组就可以将两个”单身狗“数字分别放到不同的组中,同时会将其余两两相同的数字分到他们两边,最后分别异或即可得到结果。

可能文字描述不够直观,下面以nums = [1,2,1,3,2,5]为例,画图讲解:

在这里插入图片描述

理论成立,实践开始:

    public static int[] sigleNumbers(int[] array) {
        int[] nums=new int[2];
        int tmp=0;
        int i=0;
        
        //整体异或
        for (i = 0; i < array.length; i++) {
            tmp^=array[i];
        }
        
        //寻找二进制位为1的位,用于分组
        for (i=0;i<32;i++) {
            if(((tmp>>>i)&1)==1) {
                break;
            }
        }
        
        int num1=0;
        int num2=0;
        //分组异或
        for (int j = 0; j < array.length; j++) {
            if(((array[j]>>>i)&1)==1) {
                num1^=array[j];
            } else {
                num2^=array[j];
            }
        }
        nums[0]=num1;
        nums[1]=num2;
        return nums;
    }

测试结果:



------------------ (本章完)------------------

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式