题目描述

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 最多两次 。请你找出所有出现 两次 的整数，并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间（不包括存储输出所需的空间）的算法解决此问题。

示例 1：

输入：nums = [4,3,2,7,8,2,3,1]
输出：[2,3]

示例 2：

输入：nums = [1,1,2]
输出：[1]

示例 3：

输入：nums = [1]
输出：[]

提示：

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n
  • nums 中的每个元素出现 一次 或 两次

解题思路

因为题干中 一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，很自然想到桶排序的思路。也就是利用数组索引来表示数字的值，用数组的值来表示数字的出现情况。当然在这里题干给出了限制条件，需要实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法。所以使用桶排序的思路，但需要进一步优化，直接在原数组上进行操作。将原数组中每一个值都放到对应的索引上。比如 nums[0] = 1、nums[1] = 2、nums[2] = 3、nums[3] = 4、nums[4] = 5、nums[5] = 6、nums[6] = 7、nums[7] = 8。如果发现该索引已经有值了，就说明这个值已经出现过了。我们就将这个值加入结果数组中，并将当前位置的值设置为 -1。这样就可以避免重复加入结果数组。最后返回结果数组即可。

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
func findDuplicates(numbers []int) []int {
	duplicates := make([]int, 0)

	for i := 0; i < len(numbers); i++ {
		current := numbers[i]
		for i != current-1 {
			target := numbers[current-1]
			if target == -1 {
				numbers[current-1] = current
				numbers[i] = -1
				break
			}

			if target == current {
				duplicates = append(duplicates, current)
				numbers[i] = -1
				break
			}

			// swap
			numbers[current-1] = current
			numbers[i] = target
			current = target
		}
	}

	return duplicates
}

进一步优化代码，也可以在原数组上操作后不直接将重复值设置为 -1，而是在所有值都放到对应的索引上后，再遍历一遍数组，将所有无法放入正确位置上的值加入结果数组中。

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
func findDuplicates(numbers []int) []int {
	for i := 0; i < len(numbers); i++ {
		current := numbers[i]
		for i != current-1 {
			target := numbers[current-1]

			if target == current {
				break
			}

			// swap
			numbers[current-1] = current
			numbers[i] = target
			current = target
		}
	}

	duplicates := make([]int, 0)
    for i, num := range numbers {
        if i+1 != num {
            duplicates = append(duplicates, num)
        }
    }

	return duplicates
}