[JAVA] LeetCode 136 - Single Number

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

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

 

비어있지 않은 정수형 배열이 주어진다. 모든 요소는 한 개를 제외하고 두 번씩 나타난다. 한 개인 요소를 찾아라.

Follow up : 추가 메모리를 사용하지 않고 구현해라!

 

풀이 방법

1. 주어진 배열을 오름차순으로 정렬한다.

2. 배열의 길이가 1이라면 첫 번째 요소를 리턴한다. (탐색할 필요가 없으므로)

3. 반복문 : 배열의 현재 요소(index=0)와 다음 요소(index=1)를 비교하여 값이 다를 경우 현재 요소의 값을 리턴한다.

4. 배열은 전체 인덱스를 비교하지 않고, 짝수 인덱스에서만 다음 요소와 비교가 가능하게끔 조건을 주었다.

5. 반복문 안에서도 서로 다른 요소를 찾지 못하였다면, 마지막 인덱스의 요소를 리턴한다.

 

ex) 정렬된 배열의 상태가 { 1, 1, 2, 2, 3, 4, 4 } 라면 반복문을 돌면서 배열의 index = 0, 2, 4가 탐색된다.

- i=0 (index) 일 때, nums[0] != nums[0+1] 조건은 두 요소(1,1)가 모두 1이므로 false

- i=2 (index) 일 때, nums[2] != nums[2+1] 조건은 두 요소(2,2)가 모두 2이므로 false

- i=4 (index) 일 때, nums[4] != nums[4+1] 조건은 두 요소(3,4)가 서로 다르므로 true, 현재 요소의 값 3을 리턴

 

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

 

 

 

 

 

끄적이는 글...

같이 스터디를 하는 팀원 분들의 코드를 살펴보니.. 다들 비트 연산자로 풀이하였더라..

비트 연산자를 사용하는 것이 아직 익숙하지 않고 어려운 나는 상상도 할 수 없었던 풀이 방법이었다... 또륵

비트 연산자에 대한 이해가 조금 더 깊어지면 다음 번엔 비트 연산자를 이용해서 이 문제를 풀이해보아야겠다!