[LeetCode] 136. Single Number

Problem

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Constraints:

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

Solution

Logic

1. 배열 내 모든 요소는 정수이며 비트로 구성되어 있다. 같은 값을 가진 요소끼리 XOR 비트 연산을 수행하면 0을 반환한다.

2. 배열 내 모든 요소끼리 XOR 비트 연산을 수행하면 두 번 등장하지 않는 요소의 값을 반환하게 된다.

   Code

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

   Time Complexity

   • 배열 nums의 길이를 n이라 가정할 때, 코드의 수행 시간을 좌우하는 것은 for반복문의 n번의 계산 횟수이다. 따라서 본 솔루션은 O(n)의 시간 복잡도를 갖는다.