LeetCode 136 Single Number

Problem: 

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

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

Summary:  

整型数组中出了一个元素，其余元素均出现两次。在线性复杂度且不占用多余空间的情况下，找到这个特殊元素。

Solution: 

1、最简单的方法，n*n循环，但复杂度O(n²)

2、给数组排序，前后两两元素比较。

3、XOR运算：偶数个相同的整型数XOR运算后，结果为0。0与任何数异或均得原数。

    由于数组中除目标数之外其余元素均出现两次，将数组中所有元素异或，最终所得结果即为目标数。

1 class Solution { 2 public: 3 int singleNumber(vector<int>& nums) { 4 int res = 0, len = nums.size(); 5 for (int i = 0; i < len; i++) { 6 res ^= nums[i]; 7 } 8 9 return res; 10 } 11 };

 

转载于:https://www.cnblogs.com/VickyWang/p/5988912.html

相关资源：JAVA上百实例源码以及开源项目