136. Single Number 「只出现一次的数字」

2019年11月27日 53点热度 0人点赞 0条评论

给定一个非空的整数数组,每个数字都出现次,只有一个数字例外只出现一次。找到那唯一的一个数字。

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

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

这个题,头脑爆炸💥,如果是没怎么接触过异或运算的话,想破脑袋也想不到这样的解法。这个解法主要利用了一个异或运算的性质,即 x ⊕ x = 0,将数组中所有的数字都异或运算之后,最终的值自然就是落单的那个数了。

/*
 * 136. Single Number
 * https://leetcode.com/problems/single-number/
 * https://realneo.me/136-single-number/
 */

public class SingleNumber {
    public static void main(String[] args) {
        SingleNumber solution = new SingleNumber();

        int[] nums;
        nums = new int[]{2, 2, 1};
        System.out.println(solution.singleNumber(nums));
        nums = new int[]{4, 1, 2, 1, 2};
        System.out.println(solution.singleNumber(nums));
    }

    private int singleNumber(int[] nums) {
        int x = 0;
        for (int i : nums)
            x ^= i;
        return x;
    }
}

Neo

与卿再世相逢日,玉树临风一少年。

文章评论