一、题目描述

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

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

二、解题思路

方法一：这里补充一个知识点，异或，异或满足三个条件：

第一：任何数字与0做异或运算，结果仍然是原来的数

第二：任何数和其自身做异或运算，结果是0，

第三：异或运算满足交换律和结合律。

代入题中，其实条件一和条件二都可以用来解决这个问题，这是比较简单且高效率的方法。

方法二：快速排序。

可以先给数组排个序，然后再遍历每个元素逐一比较，这个方法结果不是太好。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VgMIEJST-1623894486374)(C:\Users\86182\AppData\Roaming\Typora\typora-user-images\image-20210617093108833.png)]

三、代码演示

异或代码演示：

class Solution {
       public int singleNumber(int[] nums) {
           /*使用异或，异或有这样的原理：1.任何数和0做异或或运算，结果仍然是原来的数                                    2.任意两个数做异或，相同为0，不同为1        */        //声明一个变量赋值为0        int zero = 0;        //利用一个foreach循环遍历，就是把nums这个数组中所有元素进行遍历        for (int num:nums){
               //将nums中的每个元素num和zero进行异或，根据性质2，如果有相同的数，经过循环两个相同的数也会经历异或操作，那时zero就是0，            zero ^=num;        }        return zero;    }}

9到12行：以示例一为例，分析一下异或过程，遍历数组[2，2，1]

第一轮循环：zero ^= num ，任何数与0做异或都是本身，此时zero=2；

第二轮循环：zero ^= num，此时就是2与2做异或，结果为0，想法就是相同的数字经过异或之后都是0；

第三轮循环：zero ^= num，这时1与0异或是1，最后返回这个数即可。

快速排序代码演示：

class Solution {
       public int singleNumber(int[] nums) {
          //先将数组排序，从小到大排序       Arrays.sort(nums);       int i;       for(i=1; i<=nums.length-1;i=i+2){
              //比较           if(nums[i]!=nums[i-1]){
                  return nums[i-1];           }       }       return nums[i-1];    }}

第6行到9行：解释一下为什么i=i+2以及判断条件nums[i]!=nums[i-1]；以示例2为例[4,1,2,1,2]，排序后[1,1,2,2,4]，

第一轮循环：比较了两个1，相等后，从第索引 i+2=3 个数开始，也就是第四个数2开始

第二轮循环：nums[i-1] = 2，这个2是第三个数2。

第三轮循环：此时i=i+2=5，num[i]越界，num[i-1]=4；最后返回它即可，也是我们要找的只出现了一次的数字。

-1] = 2，这个2是第三个数2。

总结

这两种方法中异或是首选，用快排的话不管效率还是其它复杂度方面都不太好，所以快排只是一种思路，参考就行。

转载地址：http://logki.baihongyu.com/

你可能感兴趣的文章