[leetcode] Find All Numbers Disappeared in an Array

https://leetcode.com/explore/learn/card/fun-with-arrays/523/conclusion/3270/

Explore - LeetCode

Success

 

위 문제는 n 만큼의 길이를 가진 배열이 주어졌을 때, 해당 원소의 값이 1부터 ~ n까지로 채워져야 하는데 1~n 사이에 값 중 없는 값을 찾아서 List로 반환하는 문제이다.

 

풀이 

 

먼저 주어진 배열을 HashSet에 담아 중복을 제거하였고, 반복문을 이용하여 범위를 1부터 배열의 길이까지 돌게하여 HashSet에 포함되어 있지 않은 값을 List에 담아 반환하였다. 

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        if (nums == null) return null; 
        
        Set<Integer> set = new HashSet<>();
        for (int i=0; i<nums.length; i++) {
            set.add(nums[i]);
        }
        
        List<Integer> answers = new ArrayList<>();
        for (int i=1; i<=nums.length; i++) {
            if (set.contains(i) == false) {
                answers.add(i);
            }
        }
        
        return answers;
    }
}

 

또 다른 방법으로는 HashSet을 이용하지 않고 하는 방법이 있다. 

배열 원소의 값을 인덱스 값으로 만들고 음수로 바꾸어 저장한다. 음수로 바뀐 원소는 값이 있는 상태이므로 음수로 바뀌지 않은 값만 List에 담아 반환하면 된다.

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        
        // Iterate over each of the elements in the original array
        for (int i = 0; i < nums.length; i++) {
            
            // Treat the value as the new index
            int newIndex = Math.abs(nums[i]) - 1;
            System.out.println(newIndex);
            // Check the magnitude of value at this new index
            // If the magnitude is positive, make it negative 
            // thus indicating that the number nums[i] has 
            // appeared or has been visited.
            if (nums[newIndex] > 0) {
                nums[newIndex] *= -1;
            }
        }
        
        // Response array that would contain the missing numbers
        List<Integer> result = new LinkedList<Integer>();
        
        // Iterate over the numbers from 1 to N and add all those
        // that have positive magnitude in the array
        for (int i = 1; i <= nums.length; i++) {
            
            if (nums[ ] > 0) {
                result.add(i);
            }
        }
        
        return result;
    }
}