2021-01-11Algorithm2 minutes read (About 293 words) 0 visits

[자바JAVA]136. Single Number

문제 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 연산)

1
2
3

//예시
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));
  }
}