[LeetCode] Single Number

https://leetcode.com/problems/single-number/

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 * 10^4
-3 * 10^4 <= nums[i] <= 3 * 10^4
Each element in the array appears twice except for one element which appears only once.

주어진 배열에 2개의 짝이 있는 숫자와 그렇지 않은 1개의 숫자가 있습니다.

그 하나를 찾는 문제 입니다. 예를들어 [2,2,1] 의 경우에는 2가 2개 1이 1개 있으므로 1을 리턴하면 됩니다. 문제에서 추가적인 조건을 주었는데요. 반드시 지켜야 하는 부분은 아니지만 가능하면 해보라는 얘기입니다.

 

Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?

리니어타임 컴플렉시티를 만족시키면서 추가 메모리를 사용하지 않고 문제를 풀어보라는 의미 입니다.

 

일단 100% 만족 시키는지 모르겠지만 제가 생각한 풀이를 설명하겠습니다.

 

일단 배열을 오름차순 정렬합니다. 배열 정렬에서 사실 이미 속도가 저하되는 원인을 하나 만든거 같습니다. 일단은 계속 설명하겠습니다.

 

그리고 나서 for문 하나를 생성할건데요. 이 for문은 i+=2 로 즉, 2씩 늘어납니다. 그리고 정렬된 배열을 2씩 건너가면서 숫자 2개를 검토합니다.

 

즉

for(int i = 0; i < nums.length - 2; i += 2)

가 되는데요. nums.length - 2 까지 도는 이유는 아래 코드에서 이해가 되실겁니다.

if (nums[i + 1] - nums[i] != 0) {
	return nums[i];
}

i + 1에서 i를 빼서 0이 되면 짝이 맞는다는 얘기일 것입니다. 만약 마지막 원소까지 for loop가 돌게 된다면 마지막 숫자 하나가 single number가 되는 것입니다.

 

예시로 [4,1,2,1,2]의 경우에는 [1,1,2,2,4]가 될 것이고 제 for loop는 2씩 건너 뛰기 때문에 1 - 1을 하고 2 - 2를 하고 loop가 종료되게 됩니다. 그럼 마지막에 남은 4가 답입니다.

 

아래는 소스코드 입니다.

확실히 속도는 그리 빠르지 않는거같습니다만 해결은 하였네요. 추가적으로 다른 분들은 어떻게 해결 하셨는지 찾아봐야 겠습니다.

class SingleNumber {
    public static int solution(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i += 2) {
            if (nums[i + 1] - nums[i] != 0) {
                return nums[i];
            }
        }
        return nums[nums.length-1];
    }
}