개발자 Lim

class Solution {
   public List<Integer> findDisappearedNumbers(int[] nums) {
   		// 시간복잡도 O(n) 공간복잡도 O(n)
        List<Integer> ans = new ArrayList<Integer>();
        int[] tmpArray = new int[nums.length];
        // 배열 복사 과정
        for(int i=0;i<nums.length;i++){
            tmpArray[i] = nums[i];
        }
        // 해당 값 순서의 인덱스의 값을 음수화
        for(int i=0;i<nums.length;i++){
            tmpArray[tmpArray[i]-1] = Math.abs(nums[tmpArray[i]-1])*-1;
        }
        // 음수가 아닌 값을 가진 인덱스들을 찾아 리스트에 추가
        for(int i=0;i<nums.length;i++){
            if(nums[i]<0){
                ans.add(i+1);
            }
        }
        return ans;
    }
}

조건:

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= n

의역: 정수형 배열 nums가 주어진다 해당 배열의 길이는 n이며 각 인덱스에는 1~n 까지의 수 중 하나가 들어가 있을 때

해당 배열에 없는 숫자들을 반환하라. 

-> 배열의 길이가 n 일때 해당 배열에서 1~n 중에 없는 수들을 반환해라

의역: 

1번 예시의 경우는 배열의 길이가 8임으로 1~8까지의 숫자 중 없는 수를 체크 했을 때 5와 6임으로 Output은 [5,6]

2번 예시의 경우는 배열의 길이가 2임으로 1~2까지의 숫자 중 없는 수를 체크 했을 때 2임으로 Output은 [2]

풀이: 

1. HashSet의 boolean contains() 함수 사용

class Solution {
	// 시간복잡도 contains 함수는 O(1)임으로 O(n) 공간복잡도 ?
    public List<Integer> findDisappearedNumbers2(int[] nums) {
        HashSet<Integer> set = new HashSet<Integer>();
        List<Integer> ans = new ArrayList<Integer>();
        for (int num:nums) {
            set.add(num);
        }
        for(int i=1;i<=nums.length;i++){
            if(!set.contains(i))
                ans.add(i);
        }
        return ans;
    }

 2. 주어진 배열을 기준으로 해당 값이 있으면 순서상 해당 값 인덱스 값을 -로 두어서 판별

ex nums[0]=2 라면 nums[2-1] = Math.abs(nums[2-1])*-1; (0, 1 이기 때문에 2번째 인덱스 1)

class Solution {
   public List<Integer> findDisappearedNumbers(int[] nums) {
   		// 시간복잡도 O(n) 공간복잡도 O(n)
        List<Integer> ans = new ArrayList<Integer>();
        int[] tmpArray = new int[nums.length];
        for(int i=0;i<nums.length;i++){
            tmpArray[i] = nums[i];
        }
        for(int i=0;i<nums.length;i++){
            tmpArray[tmpArray[i]-1] = Math.abs(nums[tmpArray[i]-1])*-1;
        }
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0){
                ans.add(i+1);
            }
        }
        return ans;
    }
}

2-1: 공간 복잡도를 O(1)로 개선

class Solution {
	// 시간복잡도 O(n) 공간복잡도 O(1)
	public List<Integer> findDisappearedNumbers4(int[] nums) {
        List<Integer> ans = new ArrayList<Integer>();
        int index=-1;
        for(int i=0;i<nums.length;i++){
            // 만약 이전 반복으로 음수가 된 경우
            if(nums[i]<0){
                index = nums[i]*-1-1;
            }
            // 그렇지 않은 경우
            else{
                index = nums[i]-1;
            }
            // 찾은 값의 인덱스값 을 음수화
            if(nums[index]>0){
                nums[index] = -nums[index];
            }
        }
        for(int i=0;i<nums.length;i++){
            if(nums[i]<0){
                ans.add(i+1);
            }
        }
        return ans;
    }
}

링크: https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/