Leetcode - 448. Find All Numbers Disappeared in an Array

 

[Must do Easy Question]

How to effectively use LeetCode to prepare for interviews!! - LeetCode Discuss

Find All Numbers Disappeared in an Array - LeetCode

---

문제

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input: [4,3,2,7,8,2,3,1]

Output: [5,6]

---

1부터 n 까지 숫자로 이루어진 n 사이즈의 배열이 있다. 어떤 수는 하나만 존재하고 어떤수는 두번 존재한다.

이 배열에서 1부터 n까지의 숫자중 없는 숫자를 찾아라. O(n)안에 으로 구현 해봐라.

 

1부터 n 까지의 배열을 만들어 놓고 nums에 있는 수를 빼면 될것 같다.

import java.util.*;
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> answer = new ArrayList();
        for(int i = 1 ; i < nums.length+1 ; i++){
            answer.add(i);
        }
        for(int i = 0 ; i < nums.length ; i++){
            for(int j = 0 ; j < answer.size() ; j++){
                if(nums[i] == answer.get(j)){
                    answer.remove(j);
                    break;
                }
            }
        }
        return answer;
    }
}

 

 

느리다.  Time Limit Exceed 떳다.

 

for문을 하나로 줄여보도록 한다.

 

answer를 다 만들고 빼지말고 해당사항 있는 것만 answer에 추가한다.

import java.util.*;
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> answer = new ArrayList();
        for(int i = 1 ; i < nums.length+1 ; i++){
            boolean isHere = false;
            for(int j = 0 ; j < nums.length ; j++){
                if(i == nums[j]){
                    isHere = true;
                }
            }
            if(isHere == false){
                answer.add(i);
            }
        }
        return answer;
    }
}

Time Limit Exceed 뜬다.

 

n만큼 줄여봤자 크게 다르지 않으니까 당연하지 멍청아 n^2 + n 에서 n 없앤다고 될 줄알았냐

 

오케이!

 

O(n)안에 하려면 nums 한번 loop 돌때 answer 가 완성되야 한다. 적어도 2중 루프는 없애야 되는데

 

개발 잘하시는 형이 Hash에 element가 있는지 없는지는 O(1)이라고 알려주셨다.
하핫 자료구조 다시봐야지

special thanks to https://velog.io/@ehdrms2034

ehdrms2034 (600g (Kim Dong Geun)) - velog

 

hashmap 써서 구현하니까 통과는 된다.

import java.util.*;
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        HashMap <Integer,Integer> map = new HashMap<>();
        List<Integer> answer = new ArrayList();
     
        for(int i = 0 ; i < nums.length ; i++){
            map.put(nums[i],nums[i]);
        }
        for(int i = 1; i < nums.length+1 ; i++){
            if(map.containsKey(i) == false){
                answer.add(i);
            }
        }
        
        return answer;
    }
}

Success

Details 

Runtime: 19 ms, faster than 17.73% of Java online submissions for Find All Numbers Disappeared in an Array.

Memory Usage: 49.4 MB, less than 32.08% of Java online submissions for Find All Numbers Disappeared in an Array.

 

---