[LeetCode] Array - Find All Numbers Disappeared in an Array

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new ArrayList<Integer>();
		
		for (int i = 0; i < nums.length; i++) {
			if(list.contains(nums[i]))
				continue;
			else
				list.add(nums[i]);
		}
		
		for (int i = 1; i <= nums.length; i++) {
			if(list.contains(i)) {
				list.remove(list.indexOf(i));
			}else {
				list.add(i);
			}
		}			
		
		return list;	
    }
}

이 방법은 Time Limit Exceeded

그래서, HashMap사용 (HashMap의 containsKey는 O(1)이라고 함)

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		List<Integer> list = new ArrayList<Integer>();
		
		for (int i = 0; i < nums.length; i++) {
			map.put(nums[i], nums[i]);
		}
		for (int i = 1; i <= nums.length; i++) {
			if(!map.containsKey(i))
				list.add(i);
			else
				continue;
		}		
		return list;		
    }
}

 

https://soft.plusblog.co.kr/74

자바 컬렉션(Java Collection)들의 Big O (시간 복잡도, Time Complexity)