[LeetCode][Kotlin] 448. Find All Numbers Disappeared in an Array

 

448. Find All Numbers Disappeared in an Array

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

nums[i]가 [1, n] 범위에 있는 n개의 정수로 구성된 배열이 주어지면, nums에 나타나지 않는 [1, n] 범위의 모든 정수 배열을 반환합니다.

 

Example 1:

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

Output: [5,6]

 

Example 2:

Input: nums = [1,1]

Output: [2]

 

Constraints:

• n == nums.length
• 1 <= n <= 10^5
• 1 <= nums[i] <= n

---

코드 1

• 중복된 수를 제거하고, Set 의 시간 복잡도를 이용하여 [1, n] 범위의 수 중에서 나타나지 않은 수를 찾는다.

class Solution {
    fun findDisappearedNumbers(nums: IntArray): List<Int> {
        val set = nums.toSet()
        return (1..nums.size).filterNot { it in set }
    }
}

 

코드 2

• nums 의 수들은 1 부터 n 까지의 범위를 가진다. 즉, 각 수에서 1 을 뺀 값은 인덱스를 나타낸다.
• 해당 인덱스 위치의 수를 음수로 변환한다. 단, 이미 나타난 수의 중복을 피하기 위해 절댓값을 적용한 상태에서 변환한다.

class Solution {
    fun findDisappearedNumbers(nums: IntArray): List<Int> {
        val res = ArrayList<Int>()

        for (i in nums.indices) {
            val num = Math.abs(nums[i]) - 1
            nums[num] = Math.abs(nums[num]) * -1
        }

        for ((i, v) in nums.withIndex()) {
            if (v > 0) res.add(i + 1)
        }

        return res
    }
}