只出现一次的数字

淩亂°似流年 2021-09-16 15:42 342阅读 0赞

# 只出现一次的数字 #

*  题目如下：  
    给定一个非空整数数组，除了某个元素只出现一次以外，其余每个 元素均出现两次。找出那个只出现了一次的元素。

### 实例一： ###

输入: [2,2,1]输出: 1

### 实例二： ###

输入: [4,1,2,1,2]输出: 4

--------------------

现在我们进行该题的分析，首先要找的元素只出现了一次，那么我们是不是可以遍历整个数组，如果其中那个元素个数超过一的话，则不是我们要找的元素。

*  代码如下：

public static int getNum(int[] array){
    		int len = array.length;		//数组中存储元素的个数
    		for(int i=0;i<len;i++) {
    			int count =1;			//用来记录当前正在查找元素的个数
    			for(int j=i+1;j<len;j++) {
    				if(array[i]==array[j])
    					count++;		//如果相等，则计数器加1
    			}
    			if(count==1) {
    				return array[i];	//如果该元素个数恰好为1，则返回
    			}
    		}
    		return -1;					//如果数组中没有符合条件的元素，则返回-1
    	}

--------------------

通过上面的代码可知，该段代码的时间复杂度为O(n^2)，显然不是特别适用于我们在数组长度很长时去查找该元素。  
那么我们可不可以进一步去缩减时间复杂度呢，数组中有两个元素相同，那么如果该数组排序后，那么是不是也就是说这两个相同元素相邻，我们只需要找到相邻但不相等的元素，那么该元素就是个数为一的那个元素，而我们的目标则是缩短排序所用的时间复杂度。  
![在这里插入图片描述][70]

*  代码如下：

public static int getNum(int[] array){
    		Arrays.sort(array);			//使用java自带的类库,对数组进行快速排序
    		int len = array.length;
    		if(len%2==0)				//注意这里为什么要区分奇数和偶数
    		{
    			for(int i=0;i<len;i+=2)			//注意这里需累加2
    			{
    				if(array[i]!=array[i+1])		//区分奇数和偶数的原因正是这里，会发生越界
    					return array[i];
    			}
    		}
    		else
    		{
    			for(int i=0;i<len-1;i+=2)		//注意这里的条件
    			{
    				if(array[i]!=array[i+1])
    					return array[i];
    			}
    			return array[array.length-1];	//如果只剩下一个元素
    		}
    		return -1;						//数组不符合条件，则返回-1
    	}

--------------------

上面的代码时间复杂度为O(nlogn)（因为快排的时间复杂度如此）,那么可能你觉得时间复杂度还是很大，还想要进一步缩减时间复杂度，有没有办法了呢，答案是有的，那便是利用桶排序的思想。  
![在这里插入图片描述][70 1]  
我们只需要在桶中找那个个数为一的即可，它的下标就是我们要找的元素。

public static int getNum(int[] array){
    		
    		int[] bucket = new int[10000];	//为桶开辟足够大的空间
    		
    		int len = array.length;		//数组中存储元素的个数
    		for(int i=0;i<len;i++) {
    			bucket[array[i]]++;		//记录桶中存储元素的个数
    		}
    		for(int i=0;i<bucket.length;i++) {
    			if(bucket[i]==1)		//如果桶中存储该下标的个数为1
    				return i;			//返回该下标
    		}
    		return -1;					//如果数组中没有符合条件的元素，则返回-1
    	}

通过上面代码，可知其有一个很明显的漏洞，当数组中存在负数时，该段代码不能返回正常运行。但我们只需要再开辟一个数组，只用来记载负数的个数即可。  
该段代码的时间复杂度为O(n),但我们只记录正数就开辟了长度为10000的数组（甚至有时需要更长）,如果存在负数时，则为2倍。

--------------------

那么有没有一种时间复杂度即为O(n),又不需要额外开辟空间的方法呢？  
答案是有的，即使用^运算符。两个相同的数字异或为0，0与任何数字异或为那个数字。如下：  
![在这里插入图片描述][70 2]

![在这里插入图片描述][70 3]  
![在这里插入图片描述][70 4]  
那么数组中相互之间异或，剩下的最后那个是不是就是个数为1的元素呢，而我们只需遍历一遍数组就可以找到这个元素。  
代码如下：

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

该算法的主要思想如上，接下来我们进行输入的处理。  
例如我们输入\[1,1,2\],这是一个字符串，并不是数组，我们需要将其转为数组，才可以去传递参数。

Scanner sc = new Scanner(System.in);
    		String str = sc.nextLine();					//从键盘输入一行字符串
    		str = str.substring(1, str.length()-1); //截取字符串，去掉字符串中的"["和"]"
    		String[] split = str.split(",");				  //将字符串以","分割，转为一个字符串数组
    		int[] array = new int[split.length];
    		for(int i=0;i<array.length;i++)
    			array[i] = Integer.parseInt(split[i]);//将字符串转为int值
    		System.out.println(getNum3(array));

**本次分析到此，如有错误，请多多指正。**

[70]: /images/20210813/abbe6cdc84e64d189cd5010771412960.png
[70 1]: /images/20210813/3c83d20227c14dc49379f093d2e92bf5.png
[70 2]: /images/20210813/f46df54b15f643479c6b032a5ab22cf3.png
[70 3]: /images/20210813/44eef2909b43480a935337baafe1d66d.png
[70 4]: /images/20210813/07fcbe1049a742788ad9a13987959ea4.png