问题

给定一个数组，只会存在一个不重复元素，其余都为重复元素。求不重复元素值。

思路

1）利用set自动去重，遍历数组向set中添加，如果添加失败，则代表出现重复元素，则删除该元素。最终set中的值就是数组中的不重复元素。（该方式效率较低）
2）利用异或操作。

相异为真、相同为假。
任何数异或自身都为0。
任何数异或0都为自身。

实现

1)set方式实现

public class SingleNumber {

    public static void main(String[] args) {
        int[] nums = new int[]{4,1,2,1,2};
        System.out.println(singleNum1(nums));
    }

    private static int singleNum1(int[] nums) {
        /**
         * 首先不重复的元素在元素中只会存在一个
         * 利用set自动去重，如果添加失败，代表存在，则删除这个元素。 最终存在的就是不重复的。
         */
        Set<Integer> set = new HashSet<>();

        for (int num : nums) {
            if (!set.add(num)){
                //添加失败
                //删除set中该元素
                set.remove(num);
            }
        }
        return (int)set.toArray()[0];
    }
}

image.png

2）异或操作实现

public class SingleNumber {

    public static void main(String[] args) {
        int[] nums = new int[]{4,1,2,1,2};
        System.out.println(singleNum2(nums));
    }

    private static int singleNum2(int[] nums) {
        /**
         * 异或运算：
         * 相异为真，相同为假
         * a^a=0 , a^0=a
         * 任何数和相同值异或都为0
         * 任何数和0异或都为自身
         * 那么原数组可想象为：   4,1,1,2,2 = 4
         */
        int result = 0;
        for (int num : nums) {
            result = result ^ num;
        }
        return result;
    }

image.png