1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// @Title: 找到所有数组中消失的数字 (Find All Numbers Disappeared in an Array)
// @Author: 15816537946@163.com
// @Date: 2020-06-25 07:15:36
// @Runtime: 520 ms
// @Memory: 8.4 MB
/*
 * @lc app=leetcode.cn id=448 lang=golang
 *
 * [448] 找到所有数组中消失的数字
 *
 * https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/description/
 *
 * algorithms
 * Easy (52.88%)
 * Likes:    201
 * Dislikes: 0
 * Total Accepted:    14.3K
 * Total Submissions: 27.1K
 * Testcase Example:  '[4,3,2,7,8,2,3,1]'
 *
 * 给定一个范围在  1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。
 *
 * 找到所有在 [1, n] 范围之间没有出现在数组中的数字。
 *
 * 您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
 *
 * 示例:
 *
 *
 * 输入:
 * [4,3,2,7,8,2,3,1]
 *
 * 输出:
 * [5,6]
 *
 *
 */

func findDisappearedNumbers(nums []int) []int {
    ret := make([]int, 0)

	for i := range nums {
		for nums[i] != nums[nums[i]-1]  {
			nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
		}
	}

	for i, v := range nums {
		if v != i+1 {
			ret = append(ret, i+1)
		}
	}

	return ret
}