Java位运算的应用（异或运算）-求数组中唯一只出现一次的元素（LeetCode136）

145 阅读 0 评论 96 点赞

我是靠谱客的博主和谐向日葵，这篇文章主要介绍Java位运算的应用（异或运算）-求数组中唯一只出现一次的元素（LeetCode136），现在分享给大家，希望可以做个参考。

在算法题中，异或运算是一种常用的位运算方法，本文将介绍利用异或运算来求数组中唯一只出现一次的元素。

异或运算的三点重要性质如下：

任何数与0的异或运算结果等于他本身，即a⊕0=a;
任何数与其本身的运算结果等于0，即a⊕a=0;
异或运算满足交换律和结合律，即a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number

思路：在本题中，由于对空间复杂度的要求，所以使用哈希表来存储结果会导致内存不符合要求。因为数组中只有一个数仅出现过一次，所以重复出现的元素异或结果为0，0对目标元素的异或结果就等于该元素，故使用异或运算满足题目要求。

代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public static void main(String[] args) {
        int nums[]={4,1,2,1,2};
        System.out.println(singleNumber(nums));
    }
    public static int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        
        return res;
    }
}