只出现一次的数字

package com.memorys.test;
import java.util.HashSet;import java.util.Set;
/** * * 题目来源于： * https://leetcode-cn.com/leetbook/read/top-interview-questions/xm0u83/ * * @Description: * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素 * @Date: 2021-7-29 12:49 * @return */public class Main {
    public static void main(String[] args) {
        int[] arr1 = {1,5,2,2,3,3,4,4,5,6,1};        int result1 = getOnly1(arr1);        System.out.println(result1);
        int[] arr2 = {1,5,2,2,3,3,4,4,5,6,1};        int result2 = getOnly2(arr2);        System.out.println(result2);
        int[] arr3 = {1,5,2,2,3,3,4,4,5,6,1};        int result3 = getOnly2(arr3);        System.out.println(result3);

    }

    /**     * @Description: 思路：     * 因为是要取唯一的的数字，其余数字只出现两次，     * 因此，只要相同的数字能相互抵消掉，那么剩下的就是唯一的数字。     * 位运算里的异或运算刚好符合这个场景     *     * 会消耗 O(1) 的空间，但是可以通过将result变量初始赋值为 数组中的第一个值，避免额外空间的消耗。     * 时间复杂度O(n) 需要循环遍历一次 数组，并且需要对每个元素进行一次位运算， 总次数为 2n     *     * 异或运算描述：如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。     * <a>https://baike.baidu.com/item/%E5%BC%82%E6%88%96/10993677?fromtitle=%E5%BC%82%E6%88%96%E8%BF%90%E7%AE%97&fromid=720417&fr=aladdin</a>     *     * @Date: 2021-7-29 13:21     * @param arr     * @return int     */    public static int getOnly1(int[] arr){
        if (arr == null || arr.length == 0){            throw new RuntimeException("数组参数不能为空");        }
        int result = 0;        for (int i = 0; i < arr.length; i++) {            result = result ^ arr[i];        }        return result;            }

    /**     * @Description: 思路：     * 要获得唯一的元素，那么就需要把重复的元素删除掉。     * 用hash表可以使用O(1) 的时间复杂度来 进行元素的对比     * 发现重复的删除即可     *     * 时间复杂度O(n)，需要循环一次，并且每个元素要进行一次比较 总共2n次     * 空间复杂度O(n)，需要最多 n/2 的空间存储hash表的不重复元素     *     * 扩展：     * 如果重复的元素出现次数不限制，可以 > 2次     * 则可以用hashMap来存储数据，每次判断重复，则value值 +1     * 最终遍历hashMap，获取value == 1 的数据即可     * 时间复杂度 O(n)：循环n次，比较n次，赋值或者加次数     *     * @Date: 2021-7-29 13:21     * @param arr     * @return int     */    public static int getOnly2(int[] arr){
        if (arr == null || arr.length == 0){            throw new RuntimeException("数组参数不能为空");        }
        Set<Integer> hashset = new HashSet<>();        for (int i = 0; i < arr.length; i++) {            if (hashset.contains(arr[i])){                hashset.remove(arr[i]);                continue;            }            hashset.add(arr[i]);        }        return hashset.iterator().next();    }

    /**     * @Description: 思路：     * 常规思路，也是最慢的，类似冒泡     * 时间复杂度 O(n²)     * 空间复杂度 : 没有用额外的空间     *     * @Date: 2021-7-29 13:21     * @param arr     * @return int     */    public static int getOnly3(int[] arr){
        if (arr == null || arr.length == 0){            throw new RuntimeException("数组参数不能为空");        }
        for (int i = 0; i < arr.length; i++) {            int result = arr[i];            for (int j = i + 1; j < arr.length; j++) {                if (result == arr[j]){                    continue;                }            }            return result;        }        throw new RuntimeException("居然没找到不重复的元素");    }}