问题:找到所有数组中消失的数字
给定一个范围在 1 ≤ a[i] ≤ n (n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
输入:[4,3,2,7,8,2,3,1]
输出:[5,6]
解题思路:
数组中每个元素对应一个下标。n 个长度的数据array,对应下标位0 -> n-1。
如果按递增顺序存放,则 array = {1,2,....n-1}。则 array[i] = i+1。即可以通过下标来确认对应的元素是否存在。同理,可以通过元素判定下标。
则array[i] - 1 = i 能判断对应的元素是否存在
即
(1) array[0] - 1 = 3, 对应的元素存在,如存在,则取负值。
[4,3,2,7,8,2,3,1]数组变为 -> [4,3,2,-7,8,2,3,1]
(2) array[1] - 1 = 2, —> [4,3,-2,-7,8,2,3,1]
(3) array[2] - 1 < 0, 为了保证映射关系,取对应的绝对值减 1
即 Math.abs(array[1]) - 1 = 1 —> [4,-3,-2,-7,8,2,3,1]
(4) array[3] - 1 < 0, 为了保证映射关系,取对应的绝对值减 1
即 Math.abs(array[1]) - 1 = 6 —> [4,-3,-2,-7,8,2,-3,1]
(5) array[4] - 1 = 7 —> [4,-3,-2,-7,8,2,-3,-1]
(6) array[5] - 1 = 1 —> [-4,-3,-2,-7,8,2,-3,-1]
(7) Math.abs(array[6]) - 1 = 2 对应值已为负数
(8) Math.abs(array[7]) - 1 = 0 对应值已为负数
则结果 标记后的数组[-4,-3,-2,-7,8,2,-3,-1] 中不为 负的数,其对应的值不存在。
值为 i+1。
即为index(4,5)+ 1 为 5, 6.