一, 题目
给定一个整数数组 a, 其中 1 ≤ a[i] ≤ n (n 为数组长度), 其中有些元素出现两次而其他元素出现一次.
找到所有出现两次的元素.
你可以不用到任何额外空间并在 O(n) 时间复杂度内解决这个问题吗?
示例:
输入:
[4,3,2,7,8,2,3,1]
输出:
[2,3]
二, 题解
解法 1: 哈希表
遍历给定数组时, 可以查看该元素是否存在于哈希表中, 若不存在, 则将该元素存到哈希表中, 反之则是重复的元素.
但这个方法用到了额外空间, 所以看看就好咯.
时间复杂度: O(n), 空间复杂度: O(n)
- func findDuplicates(nums []int) []int {
- len := len(nums);
- if len <= 1 {
- return nil
- }
- hashMap := make(map[int]int)
- result := []int{}
- for _, v := range nums {
- _, exist := hashMap[v];
- if (exist) {
- result = append(result, v)
- } else {
- hashMap[v] = v
- }
- }
- return result
- }
解法 2: 交换法 -- 原地哈希
因为题目说了, 数组里的所有数字都在 1 ~ n 的范围内 (n 是数组长度), 但数组的下标是从 0 开始, 所以可以遍历数组, 使数组的索引和值建立对应的关系, 也就是索引为 0 时, 值为 1, 索引为 1 时, 值为 2, 以此类推.
遍历元素时,
当 a[i] != i+1 时, 就将位置 i 和 a[i]-1 上的两个值交换, 反之则 i 移动到下一位.
当 a[i] == a[a[i]-1] 时, 表示 a[i] 有重复, 记录重复数字, 并把下标 i 上的数字置为 0.
当 i 上的数字是 0 时, i++
遍历到数组末尾, 结束
时间复杂度: O(n), 空间复杂度: O(1)
- func findDuplicates(nums []int) []int {
- len := len(nums)
- if len <= 1 {
- return nil
- }
- result := []int{}
- i := 0
- for i < len {
- if i == nums[i] - 1 || nums[i] == 0{
- i++
- continue
- }
- if nums[i] == nums[nums[i] - 1] {
- result = append(result, nums[i])
- nums[i] = 0
- i++
- } else {
- nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]
- }
- }
- sort.Ints(result)
- return result
- }
来源: https://www.cnblogs.com/sunshineliulu/p/12953831.html