[LeetCode] 자바 136. Single Number

136. Single Number

Easy

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

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

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

Example 2:

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

---

문제는 간단합니다. int array 가 들어오는데 거기서 홀로 있는 number를 찾아서 return 하시오.

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

첫 시도.
int array를 정렬하고 홀수인덱스 숫자와 짝수인덱스 숫자를 비교하면서 없는거 찾기. 이때 for문을 다 돌았는데도 없으면 마지막 숫자가 홀로 있는 숫자라는 아이디어입니다.

아직 개선할 점이 많이 보입니다.

두번째 시도.
아무래도 정렬은 시간이 오래걸리니 정렬을 하지말고 하는 방식을 생각해봅니다. 일단 리스트를 하나 선언합니다. 들어오는 순서대로 읽으면서 리스트에 넣는데, 넣기 전에 리스트에 있는지 확인합니다. 만약 있는 숫자면 리스트에서 제거, 없으면 새로 넣기를 반복해보겠습니다. 

class Solution {
    public int singleNumber(int[] nums) {
        ArrayList<Integer> numList = new ArrayList<>();
        for ( int i = 0 ; i < nums.length; i++){
            int targetNum = nums[i];
            int index = numList.indexOf(targetNum);
            if(index >=0){
                numList.remove(index);
            }else{
                  numList.add(targetNum);
            }

        }
      
          return numList.get(0);
    }
}

네. 좋습니다. 메모리는 좋아졌는데 속도면에서 엄청 안좋아졌군요 ㅋㅋㅋㅋ 어디서 시간이 많이 걸리는지 모르겠습니다. arraylist자체가 많이 잡아먹는 듯한데.. 결국 최종솔루션을 보고 정답을 확인해야겠습니다.

 

class Solution {
  public int singleNumber(int[] nums) {
    HashMap<Integer, Integer> hash_table = new HashMap<>();

    for (int i : nums) {
      hash_table.put(i, hash_table.getOrDefault(i, 0) + 1);
    }
    for (int i : nums) {
      if (hash_table.get(i) == 1) {
        return i;
      }
    }
    return 0;
  }
}

정답은 hash map 였습니다. 역시 hash map은 빠르..? 제가 처음에 짠 코드보다 느렸습니다. ㅜㅜ 그래도 이 코드는 살펴볼 가치가 있어서 한번 보겠습니다.

여기서 hashmap의 gerOrDefault에 대해 간략히 설명하겠습니다.

getOrDefault

default V getOrDefault(Object key, V defaultValue)

찾는 키가 존재한다면 찾는 키의 값을 반환하고 없다면 기본 값을 반환한다.

그래서 위의 코드를 살펴보면

hash table에 값을 넣는데 그 전에 같은 위치에 값이 없으면 값에 1일 넣고 있으면 해당값을 가져온뒤 +1 의 값을 넣습니다.

결과적으로 하나있는 숫자는 1를 두개있는 숫자는 2를 가지고 있게 됩니다. ( 만약 여러개가 들어온다면 같은 코드로 그대로 사용 가능한 감탄스러운 코드입니다.)

그래서 hash map를 돌면서 값이 1인 경우를 찾으면 끝입니다.