问题描述

这是LeetCode上的一道算法题，笔者整理了三种解题思路和方法，希望可以帮助大家提升算法的思维。

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

说明：

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

示例 1:

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

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

来源：力扣（LeetCode）
链接：136.只出现一次的数字

一、解法1（双指针双引用暴力求解）：

注意题设，不能使用额外空间来求解，那么就不用想着用Map求解了。首先给出一个时间复杂度为O（n*n）的算法。
设置2个指针i和j，双重for循环遍历，用计数器变量count记录每个数字出现的次数，代码如下：

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

    private static int find(int[] arr) {
        for (int i =0;i<arr.length;i++) {
            int count=0;
            for (int j = 0; j <arr.length; j++) {
                if (arr[i]==arr[j]){
                  count++;
                }
            }
            if (count==1){
                return arr[i];
            }
        }
        return -1;
    }

内循环结束，刷新count计数器的值，记录每个元素出现的次数，当循环遍历一次之后发现当前元素count为1（只出现一次）时，返回这个值。

二、解法2（排序后与左右元素比较）

先调用Arrays工具类里面的sort排序算法，排序算法最快最优的时间复杂度也得是O（nlogn），排好序后，若这个数字和左右相邻的数字都不一样，就返回这个值。（第一个元素和最后一个元素单独考虑）。代码如下：

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

    private static int find(int[] arr) {
        if (arr.length == 1) 
            return arr[0];
        Arrays.sort(arr);
        //第一个和最后一个单独考虑
        if (arr[0] != arr[1]) 
            return arr[0];
        if (arr[arr.length - 1] != arr[arr.length - 2])
            return arr[arr.length - 1];
        for(int i = 1; i < arr.length - 1; i++){
            if(arr[i] != arr[i + 1] && arr[i] != arr[i - 1])
                return arr[i];
        }
        return -1;
    }

三、解法3（异或运算巧解）

下面介绍一个官方给出的时间复杂度只有O（n）的算法。（要是能自己想的出来这个方法的都是大佬~）。
先引出异或运算的定义：

异或（eor）是一个数学运算符。.它应用于逻辑运算。.异或的数学符号为”⊕”，计算机符号为”eor”。.其运算法则为：
如果a、b两个值不相同，则异或结果为1。.如果a、b两个值相同，异或结果为0。
异或也叫半加运算，其运算法则相当于不带进位的二进制加法：二进制下用1表示真，0表示假，则异或的运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1），这些法则与加法是相同的，只是不带进位，所以异或常被认作不进位加法。

异或运算的特征：

任何数和 0 做异或运算，结果仍然是原来的数，即 a ⊕ 0=a。

任何数和其自身做异或运算，结果是 00，即 a ⊕ a=0。

异或运算满足交换律和结合律，即 a ⊕ b ⊕ a = b ⊕ a ⊕ a = b ⊕ (a ⊕ a)= b ⊕ 0 = b

这是一个按位异或的运算过程，比如3的二进制位是0011，1的二进制位是0001，那么1⊕ 3 =0011⊕0001=0010=2。
最关键的是，要是两个数相同，异或结果为0！！
那么这题的思路就来了：把所有数字都做异或运算，那么最后的结果一定是单独的最后那个数字（异或运算满足交换律和结合律），例如这题：3⊕2⊕3⊕4⊕6⊕6⊕2 =（3⊕3）⊕（2⊕2）⊕（6⊕6）⊕4 = 0⊕4=4
代码如下：

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

    private static int find(int[] arr) {
        int ret = 0;
        for (int i : arr) {
            ret ^= i;
        }
        return ret;
    }