题目描述:
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
解决思路一：用Map存储出现的key,一次存1，超过1次存2，全部遍历存储到Map后再遍历Map判断（PS:不推荐）
缺点: 增加了额外的空间，进行了两次遍历
优点:可进行拓展，查出所有唯一值及所有重复值出现的次数等
class Solution {
public int singleNumber(int[] nums) {
Map<Integer,Integer> params = new HashMap<>(nums.length);
Integer key;
for (int i = 0; i < nums.length; i++) {
key = nums[i];
if (params.containsKey(key)){
params.put(key,2);
}else {
params.put(key,1);
}
}
for(Map.Entry<Integer, Integer> entry: params.entrySet()){
if (entry.getValue() == 1){
return entry.getKey();
}
}
throw new RuntimeException("没有找到");
}
}
解决思路2:利用Set天然唯一性去重，不存在则添加，存在则删除，最后Set集合中剩余的那个值就是唯一值（PS:不推荐）
缺点:增加了额外的空间，每次添加新元素则需要判断是否已经存在
class Solution {
public int singleNumber(int[] nums) {
Set<Integer> n = new HashSet<Integer>();
for(int i=0;i<nums.length;i++) {
if(n.contains(nums[i])){
n.remove(nums[i]);
}else{
n.add(nums[i]);
}
}
Iterator it = n.iterator();
while (it.hasNext()) {
int i = (int)it.next();
return i;
}
return 0;
}
}
解决思路三:排序后，奇偶位两数比较，出现不相等的情况则其中比有一个是唯一数，不相等，则奇数位的值为唯一值(不推荐)
缺点:需要先进行排序，数组乱序的复杂度直接影响了运行的时间
classSolution{
publicintsingleNumber(int[] nums){
Arrays.sort(nums);
int i=0,j=1;
while (i<nums.length&&j<nums.length) {
if (nums[i]==nums[j]) {
//奇偶位两数比较
i=i+2;
j=j+2;
}
else {
break;
}
}
if (i<nums.length&&j<nums.length) {
return nums[i];
}
else {
return nums[nums.length-1];
}
}
}
解决思路四:利用异或运算符（^）进行计算，相同数则相互抵消为0，运算后最后剩余的值为唯一值（推荐）
优点:不需要额外申请空间，只进行了一遍运算，且异或运算速度快
classSolution{
publicintsingleNumber(int[] nums){
for (int i = 1, len = nums.length; i < len; i += 2) {
nums[0] ^= nums[i] ^ nums[i+1];
}
return nums[0];
}
}
总结:个人比较喜欢思路一及思路四，思路一拓展性比较强，思路四性能好。
