[자바JAVA]136. Single Number

💡 핵심 요약 (TL;DR)

'136. Single Number' 알고리즘 문제의 요구사항을 분석하고 최적의 자료구조와 연산 방식을 적용해 구현한 풀이다. * 모든 릿코드(LeetCode)(leetcode) java 풀이을 확인했다.

문제 136. Single Number

주어진 array안에 쌍이 아닌 홀로 있는 숫자를 찾는 문제이다.
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

• 입출력예시

//예시1
Input: nums = [2,2,1]
Output: 1

//예시2
Input: nums = [4,1,2,1,2]
Output: 4

//예시3
Input: nums = [1]
Output: 1

풀이 코드 1 : 비트연산자

• 비트 연산자(^) : 대응되는 비트가 서로 같으면 0을, 다르면 1을 반환함. (비트 XOR 연산)

//예시
a^a = 0
a^1 = 1

• Runtime 1 ms Memory 47.9 MB

public class _0136SingleNumber {
  public static int singleNumber(int[] nums) {

    int val=0;
    for(int i=0;i<nums.length;i++){
      val^=nums[i];
    }
    return val;

  }

  public static void main(String[] args) {
    int[] nums =// {2, 2, 1};
                //{4,1,2,1,2};
                //{1};
                //{-1,-1,-2}; //=> -2
                //{1,3,1,-1,3};
    System.out.println(singleNumber(nums));
  }
}

풀이2 : HashMap사용

• HashSet : contains()을 통해 있으면 remove, 없으면 add해서 남은 값을 출력

• Runtime 10 ms Memory 40 MB

public class _0136SingleNumber {
  public static int singleNumber(int[] nums) {

    Set<Integer> box = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        if (box.contains(nums[i])) {
            box.remove(nums[i]);
        } else {
            box.add(nums[i]);
        }
    }
    return box.stream().findFirst().get();
  }

  public static void main(String[] args) {
    int[] nums =// {2, 2, 1};
                //{4,1,2,1,2};
                //{1};
                //{-1,-1,-2}; //=> -2
                //{1,3,1,-1,3};
    System.out.println(singleNumber(nums));
  }
}

성능 비교

	비트연산자사용	해시맵사용
Runtime	1 ms	10 ms
Memory	47.9 MB	40 MB

다른 문제 풀이가 보고싶다면?

• 모든 릿코드(LeetCode)(leetcode) java 풀이

#Leetcode