問題：
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.

方法：
n等于數(shù)組長度，同時數(shù)組中的元素都小于等于n（1 ≤ a[i] ≤ n），所以數(shù)組中的元素也可以代表數(shù)組下標（a[i]-1），只要對數(shù)組中出現(xiàn)元素對應(yīng)位置加n，則該位置元素必大于n，而沒有出現(xiàn)過的元素對應(yīng)位置元素必小于等于n，通過這種方式就可以找到?jīng)]有出現(xiàn)過的元素。

具體實現(xiàn)：

class FindDisappearedNumbers {
    fun findDisappearedNumbers(nums: IntArray): List<Int> {
        val list = mutableListOf<Int>()
        val n = nums.size
        for (i in nums.indices) {
            nums[(nums[i]-1) % n] += n
        }
        for (i in nums.indices) {
            if (nums[i] <= n) {
                list.add(i+1)
            }
        }
        return list
    }
}

fun main(args: Array<String>) {
    val array = intArrayOf(4, 3, 2, 7, 8, 2, 3, 1)
    val findDisappearedNumbers = FindDisappearedNumbers()
    val result = findDisappearedNumbers.findDisappearedNumbers(array)
    for (no in result) {
        println("$no ")
    }
}

有問題隨時溝通

具體代碼實現(xiàn)可以參考Github