扫码订阅《 》或入驻星球,即可阅读文章!

GOLANG ROADMAP

阅读模式

  • 沉浸
  • 自动
  • 日常
首页
Go学习
  • Go学院

    • Go小课
    • Go小考
    • Go实战
    • 精品课
  • Go宝典

    • 在线宝典
    • B站精选
    • 推荐图书
    • 精品博文
  • Go开源

    • Go仓库
    • Go月刊
  • Go下载

    • 视频资源
    • 文档资源
Go求职
  • 求职服务

    • 内推互助
    • 求职助力
  • 求职刷题

    • 企业题库
    • 面试宝典
    • 求职面经
Go友会
  • 城市
  • 校园
推广返利 🤑
实验区
  • Go周边
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
author-avatar

GOLANG ROADMAP


首页
Go学习
  • Go学院

    • Go小课
    • Go小考
    • Go实战
    • 精品课
  • Go宝典

    • 在线宝典
    • B站精选
    • 推荐图书
    • 精品博文
  • Go开源

    • Go仓库
    • Go月刊
  • Go下载

    • 视频资源
    • 文档资源
Go求职
  • 求职服务

    • 内推互助
    • 求职助力
  • 求职刷题

    • 企业题库
    • 面试宝典
    • 求职面经
Go友会
  • 城市
  • 校园
推广返利 🤑
实验区
  • Go周边
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
  • 面试宝典系列

    • 剑指 Offer 题解
  • 数组与矩阵

    • 3. 数组中重复的数字
    • 4. 二维数组中的查找
    • 5. 替换空格
    • 29. 顺时针打印矩阵
    • 50. 第一个只出现一次的字符位置
  • 栈队列堆

  • 双指针

  • 链表

  • 树

  • 贪心思想

  • 二分查找

  • 分治

  • 搜索

  • 排序

  • 动态规划

  • 数学

  • 位运算

  • 其他

扫码订阅《 》或入驻星球,即可阅读文章!

3. 数组中重复的数字


GOLANG ROADMAP

# 题目链接

牛客网 (opens new window)

力扣 (opens new window)

# 题目描述

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字是重复的,也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

Input:
{2, 3, 1, 0, 2, 5}

Output:
2
1
2
3
4
5

# 解题思路

方法一:由于只需要找出数组中任意一个重复的数字,因此遍历数组,遇到重复的数字即返回。为了判断一个数字是否重复遇到,使用 map 存储已经遇到的数字,如果遇到的一个数字已经在 map 中,则当前的数字是重复数字。

package main

import (
	"fmt"
)

func findRepeatNumber(nums []int) int {
	m := make(map[int]int)
	for _, value := range nums {
		if _, ok := m[value]; ok {
			// 存在该数值
			return value
		} else {
			// 不存在
			m[value] = 1
		}
	}
	return -1
}

func main() {
	nums := []int{2, 3, 1, 0, 2, 5, 3}
	num := findRepeatNumber(nums)
	fmt.Println("重复的一个数字为: ", num)
}
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

执行用时 : 76 ms, 在所有 Go 提交中击败了 7.58% 的用户

内存消耗 : 9.1 MB, 在所有 Go 提交中击败了 100% 的用户

方法二:排序,看前后元素是否相等

package main

import (
	"fmt"
	"sort"
)

func findRepeatNumber(nums []int) int {
	// 对整型切片进行排序
	sort.Ints(nums)

	// 遍历切片, 与下一个数字重复就返回
	for i, numsSize := 0, len(nums); i < numsSize-1; i++ {
		if nums[i] == nums[i+1] {
			return nums[i]
		}
	}
	return -1
}

func main() {
	nums := []int{2, 3, 1, 0, 2, 5, 3}
	num := findRepeatNumber(nums)
	fmt.Println("重复的一个数字为: ", num)
}
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

执行用时 : 56 ms, 在所有 Go 提交中击败了 22.35% 的用户

内存消耗 : 6.9 MB, 在所有 Go 提交中击败了 100% 的用户

方法三:因为数组长度为 n, 且数字都在 0 ~ n-1 范围内,所以只需要判断下标 i 是否与 nums[i] 相等即可(如果都相等,说明没有重复元素):

  • i 与 nums[i] 相等,继续向下扫描
  • i 与 nums[i] 不相等,先比较 nums[i] 与 nums[nums[i]] 的值:
    • nums[i] 与 nums[nums[i]] 相等,返回 nums[i]
    • nums[i] 与 nums[nums[i]] 不相等,交换 nums[i] 与 nums[nums[i]] ,一直重复
package main

import (
	"fmt"
)

func findRepeatNumber(nums []int) int {
    for i := 0; i < len(nums); i++ {
        for i != nums[i] {
            if nums[i] == nums[nums[i]] {
                return nums[i]
            }
            nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
        }
    }
    return -1
}

func main() {
	nums := []int{2, 3, 1, 0, 2, 5, 3}
	num := findRepeatNumber(nums)
	fmt.Println("重复的一个数字为: ", num)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

执行用时 : 40 ms, 在所有 Go 提交中击败了 95.89% 的用户

内存消耗 : 8.9 MB, 在所有 Go 提交中击败了 23.87% 的用户

  • 题目链接
  • 题目描述
  • 解题思路