服务器建设一个自己的网站,淄博英文网站建设专业,做视电影网站赚钱吗,做网站网站怎么赚钱数组中只出现一次的两个数字 背景题目描述题解 背景
刷到此题的时候#xff0c;只写出了最普通的解法#xff0c;最后看了二进制解法#xff0c;叹为观止#xff0c;不禁感叹到它的巧妙#xff0c;因此记录一下,共勉。
题目描述
牛客地址#xff1a; https://www.nowc… 数组中只出现一次的两个数字 背景题目描述题解 背景
刷到此题的时候只写出了最普通的解法最后看了二进制解法叹为观止不禁感叹到它的巧妙因此记录一下,共勉。
题目描述
牛客地址 https://www.nowcoder.com/practice/389fc1c3d3be4479a154f63f495abff8 描述 一个整型数组里除了两个数字只出现一次其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
数据范围 数组长度 2≤n≤1000 数组中每个数的大小 0val≤1000000
要求 空间复杂度 O(1) 时间复杂度 O(n)
提示输出时按非降序排列。
示例1 输入[1,4,1,6]
返回值[4,6] 说明 返回的结果中较小的数排在前面
示例2 输入[1,2,3,3,2,9]
返回值[1,9]
题解
方法一 题目给的意思分析之后很容易想到一种方法就是用哈希表进行统计辅助得到这两个只出现一次的数字。 此方法比较简单直接给出代码
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param nums int整型一维数组 * return int整型一维数组*/public int[] FindNumsAppearOnce (int[] nums) {MapInteger,Integer numMap new HashMap();for(int i0;inums.length;i){Integer num numMap.get(nums[i]);if(null num){numMap.put(nums[i],1);}else{numMap.put(nums[i],2);}}ArrayListInteger res new ArrayListInteger();SetInteger numKeySet numMap.keySet();for(Integer numKey:numKeySet){if(numMap.get(numKey) 1){res.add(numKey);}}Collections.sort(res);int[] intRes new int[res.size()];for(int i0;ires.size();i){intRes[i] res.get(i);}return intRes;}
}本文主要对第二种解法的思路做一下整理和分析。
对于这道题目我们先来想另外一个问题
如果数组中只有一个出现了一次的数字我们想到得到它那么应该如何解决呢
我们都知道异或运算如果两个数一样则异或结果为0不一样则异或结果为1。二进制 0⊕001⊕010⊕111⊕10 举个例子 4 ⊕ 4 0将4化为二进制为 0100 所以 0100 异或 0100 得到 0000 4 ⊕ 4 ⊕ 5 5 则 0100 0100 0101 得到 0101 我们可以看到上面的运算过程因为44两者相等异或结果为0。所以0异或任意数都等于任意数。 所以当只有一个出现了一次的数字的时候则只需要将全部数进行异或运算运算结果就剩下了那个只出现一次的数字了。
public int[] singleNumber(int[] nums) {int x 0;for(int num : nums) // 1. 遍历 nums 执行异或运算x ^ num;return x; // 2. 返回出现一次的数字 x
}好了上面说了这么多那这道题目是找两个只出现一次的数字呀~
上面的方法又是针对只出现一次的数字假设我也一样全部执行异或运算 1⊕4⊕1⊕6最后也还是会剩下4⊕6呀~
我们看看
0100 ⊕ 0110 0010 这个结果也不能得出什么东西哇~
我们换个角度思考能不能做个分组将题目分为两组 然后每一组求出其中的出现一次的数字最后两者一起返回不就解决问题了吗
那么我们要如何分组呢位运算进行分组我们首先想到的应该是奇偶分组就是将所有数 1此时能将数字分为奇偶两组。
但是这个时候问题又来了你又不能保证两个数字就一奇一偶有可能都是奇数也有可能都是偶数呀~
但是我们想一下1的操作归根到底是按照二进制最低位的不同来分组的 例如 00113 010150100400011 对上面四个数分组我们都1可以分得结果 001101010001奇数 0100 偶数 我们很明显能够知道当二进制1结果为1的时候为奇数反之为偶数。它们是按照最低位的不同来分组的。
上面我们知道能够将数字分为 奇偶两组那么现在我再给出一个难度如何区分出 00110101 对 00110101 这两个数进行分组我们可以观察到最低位都为1此时如果我们还是进行1操作去分组那肯定是分不出来的 因为两数的最低为都是一样的1之后还是1还是无法区分那么我们看到最低的第二位0011是10101是0很明显这两位就不一样那么我们就可以将这两数0010呀不就能够区分出来了吗 0011 0010 0010 01010010 0000此时还是根据结果是否为0得到分组 那要是是 0100 和 1100呢如何分组呢 不就是1000 就能够分组了吗
所以说了那么多其实就是为了推出一个分组的方式两个不同的数如何分组 我们都知道两个不同的数那么它的二进制表示肯定是不一样的这是毋庸置疑的
所以我们要想对两者进行分组操作就是需要找到两者中的那一位不同的二进制然后得到分组的与值去的那个值问题不就解决了吗
那要怎么找到那一位不同的二进制呢 我们看一个例子 1146 全部做异或运算结果为 4⊕6 0100⊕0110 0010 异或的运算规则是什么 相同的为0不同的为1。所以我们根据两者异或出来的结果 0010不就可以知道那一位不同了嘛为1的那一位就是不同的 好了说了这么多下面安排代码把~ public int[] FindNumsAppearOnce (int[] nums) {//定义一个异或的值int xorRes 0;//求出所有数字的异或值for(int num:nums){xorRes^num; }//定义分组掩码,0为1组1为1组正好2组int mask 1;//寻找分组的掩码位用来分组用,掩码只能有一位是1,否则后面//进行与运算可能无法分出来因为多位的话与运算可能结果都不为0//只有一位为1掩码才能确保其中一个数字结果一定为0while((maskxorRes) 0){mask mask1;}int a0,b0;for(int num:nums){//如果与掩码做与运算等于0的分到第一组if((masknum) 0){a^num;}//否则是第二组else{b^num;}}if(ab){return new int[]{b,a};}else{return new int[]{a,b};}}复杂度分析 时间复杂度O(N)。数组的长度n循环。 空间复杂度O(1)。几个变量的空间。
备注:大部分文字转载自牛客精华题解有兴趣的可以去看一下。
