题目描述
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例:
输入: [2,2,1] 输出: 1
思路1
- 使用快速排序,将相同元素都放在相邻位置上。
2.遍历数组,每次跳跃两个元素进行寻找,若nums[i] != nums[i+1],说明nums[i]就是答案。
Java代码实现
public int singleNumber(int[] nums) { Arrays.sort(nums); for(int i=0;i<nums.length;i=i+2){ if(i+1 < nums.length && nums[i] != nums[i+1]) return nums[i]; } return nums[nums.length-1]; }
思路2
- 题中除目标元素外,都出现两次,可以利用 相同元素 异或 等于 0 的性质。
- 最终异或结果即为要寻找的元素。
Java代码实现
public int singleNumber(int[] nums) { int res = nums[0]; for(int i=1;i<nums.length;i++){ res = res ^ nums[i]; } return res; }