剑指 Offer 03. 数组中重复的数字
2024-08-29 09:02:38
剑指 Offer 03. 数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
思路
哈希表法： 由于只需要找出数组中任意一个重复的数字，因此遍历数组，遇到重复的数字即返回。为了判断一个数字是否重复遇到，使用集合存储已经遇到的数字，如果遇到的一个数字已经在集合中，则当前的数字是重复数字。时间复杂度：遍历数组O(n)，查询hash表为O(1)，整体还是为O(n)
空间复杂度：需要开辟一个数组暂存遍历的数值，所以为O(n)
func findRepeatNumber(nums []int) int {
if nums == nil || len(nums)==0 {
return -1
}
mp := map[int]int{}
for i,v := range nums{
if _,ok := mp[v];ok { //如果hash表中存在，表明出现了重复数值
return v
}
mp[v] = i
}
return -1
}
原地置换法:如果没有重复数字，那么正常排序后，数字i应该在下标为i的位置，所以思路是重头扫描数组，遇到下标为i的数字如果不是i的话，（假设为m),那么我们就拿下标m对应的值与下标m对应的值作为下标的值交换，即nums[m]与nums[nums[m]]交换。在交换过程中，如果有重复的数字发生，那么终止返回ture时间复杂度还是O(n)
降低了空间复杂度，使空间复杂度从O(n) ——>O(1)
func findRepeatNumber(nums []int) int {
if nums == nil || len(nums)==0 {
return -1
}
for i:=0;i<len(nums);i++{
//下标与对应值不等
if i!=nums[i]{
if nums[i]==nums[nums[i]]{ //说明找到了重复的值
return nums[i]
}
}
//交换
nums[i],nums[nums[i]] = nums[nums[i]],nums[i]
}
return -1
}
最新文章
- Linux 系统查看物理内存使用率的命令脚本，以百分比形式输出。
- 分享一下刚刚HP电话面试。。。。。。。。我估计我挂了，不过还是要来分享一下
- 在datagrid中实现单击行选择整行
- Mybatis与Hibernate的区别
- Oracle shutdown immediate遭遇ORA-24324 ORA-24323 ORA-01089
- sax 解析 xml
- 1.4---字符串空格变成20%（CC150）
- elasticsearch 之IK分词器安装
- Linq打印
- Angular2 和TypeScript
- IT忍者神龟之Oracle DBA经常使用查询吐血列举
- (转载)Google的PageRank算法
- RAMCloud：内存云存储的内存分配机制
- 【Matlab编程】Matlab高效编程技巧
- docker 安装 MySQL 8，并减少内存占用 记录
- 快速去水印（win10换图3D工具）
- 数据库主键到底是用自增长（INT）好还是UUID好
- sql插入oracle链接的数据
- \x 开头编码的数据解码成中文
- FJOI2019游记