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?
要求
这道题目是求数组中只出现一次的数字。
解题思路
利用异或原理。最后返回的数字为只出现一次的数组元素。
eg：[1,2,1,2,3] 因为A ^ B=B ^ A ; (A ^ B) ^ C == A ^ (B ^ C)
所以数组异或之后的结果等于： （1^1） ^ （2^2） ^ 3 = 0 ^ 0 ^ 3 = 3.
算法实现
public class Solution {
public int singleNumber(int[] A) {
if(A==null||A.length==0){
return 0;
}
int num = 0;
for(int i : A){
num^=i;
}
return num;
}
}
自己的解题思路
自己的解题太笨，因为固定思维对于数组第一件事情就是排序。
将数组按照升序排列得到 [1,1,2,2,3] 或者[1,2,2,3,3] 或者[1,1,2,3,3]有这三种情况
落单的数是第一个，最后一个，或者中间一个。
中间的数，只需判断这个数的是不是不等于两边的数即可。
算法实现
class Solution136 {
public static int singleNumber(int[] nums) {
int length = nums.length - 1;
int target = 0;
if (length == 1) {
return nums[0];
} else {
Arrays.sort(nums);
if (nums[0] != nums[1]) {
target = nums[0];
} else if (nums[length - 1] != nums[length]) {
target = nums[length];
} else {
for (int i = 1; i < length; i++) {
if (nums[i] != nums[i + 1] && nums[i] != nums[i - 1]) {
target = nums[i];
}
}
}
}
return target;
}
}
