首页 > 代码库 > leetcode136 利用异或运算找不同的元素

leetcode136 利用异或运算找不同的元素

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题目意思:找出一个数组中的一个不同的元素。

 

新手想法,先排序,然后循环找出那个前后不一样的那一个。(题目给出意思是不能运用其他数组去标记的,否则,利用一个容器去记录的话,那复杂度肯定是N的)

高手想法,利用异或的位运算。

只要任意两个相同的数异或之后都是0,那么只要把所有的元素都异或在一起,那么最后剩下的值就是没有相同的数和它一起变成0了。

public class Solution {    public int singleNumber(int[] nums) {        int result = 0;        for(int i=0;i<nums.length;i++)            result ^= nums[i];        return result;    }}

leetcode136 利用异或运算找不同的元素