Comment on page

136.Single-Number

136. Single Number

题目地址

题目描述

Given a non-empty 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?
​
Example 1:
Input: [2,2,1]
Output: 1
​
Example 2:
Input: [4,1,2,1,2]
Output: 4

代码

Approach #1 List Operation

class Solution {
public int singleNumber(int[] nums) {
List<Integer> list = new ArrayList<>();
for (int i: nums) {
if (!list.contains(i)) {
list.add(i);
} else {
list.remove(list.indexOf(i));
}
}
return list.get(0);
}
}

Approach #2 Bit Manipulation

class Solution {
public int singleNumber(int[] nums) {
int a = 0;
for (int i : nums) {
a ^= i;
}
return a;
}
}