Contents
Problem
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
Solution
Using “XOR” operation is the most efficient way to solve this problem.
Example 2:
Input: [4,1,2,1,2] Output: 4
Checkout following picture which shows the procedure of processing the example:
Code
class Solution { public int singleNumber(int[] nums) { int a = 0; for(int i = 0;i<nums.length;i++){ a^=nums[i]; } return a; } }
Detail Execution time :1 ms, beat 99.53% Java commit Memory Used :38.9 MB, beat 33.39% Java commit