当前位置:网站首页>One brush 312 - simple repetition set - Sword finger offer 03 Duplicate number in array (E)
One brush 312 - simple repetition set - Sword finger offer 03 Duplicate number in array (E)
2022-04-23 15:40:00 【Tang and Song Dynasties】
subject :
Find the repeated numbers in the array .
At a length of n Array of nums All the numbers in 0~n-1 Within the scope of . Some numbers in the array are repeated ,
But I don't know how many numbers are repeated , I don't know how many times each number has been repeated . Please find any duplicate number in the array .
---------------------------
Example 1:
Input :
[2, 3, 1, 0, 2, 5, 3]
Output :2 or 3
Limit :
2 <= n <= 100000
-------------------
Ideas : Traversal array
Because you only need to find any duplicate number in the array , So iterate through the array , If you encounter a duplicate number, return .
To determine whether a number is repeated , Use collections to store numbers that have been encountered , If you encounter a number that is already in the set ,
The current number is a duplicate number .
The initialization set is empty , Repeated numbers repeat = -1
Traversal of each element in an array :
Add this element to the collection , Judge whether the addition is successful
If the addition fails , Indicates that the element is already in the collection , So this element is a repeating element , Assign the value of this element to repeat, And end the traversal
return repeat
------------------
Complexity analysis
Time complexity :O(n)
Traverse the array once . Use hash set (HashSet), The time complexity of adding elements is O(1), Therefore, the total time complexity is O(n)
Spatial complexity :O(n). Every element that is not repeated may be stored in the collection , So occupy O(n) Extra space .
--------------------
class Solution {
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
if (set.contains(num)) return num;
set.add(num);
}
return -1;
}
}
It involves simple repetition : set
版权声明
本文为[Tang and Song Dynasties]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204231535203838.html
边栏推荐
- Today's sleep quality record 76 points
- Control structure (I)
- PHP PDO ODBC loads files from one folder into the blob column of MySQL database and downloads the blob column to another folder
- 删除字符串中出现次数最少的字符
- IronPDF for . NET 2022.4.5455
- 自主作业智慧农场创新论坛
- pywintypes.com_error: (-2147221020, ‘无效的语法‘, None, None)
- Functions (Part I)
- MySQL集群模式与应用场景
- 字符串排序
猜你喜欢
网站建设与管理的基本概念
MySQL集群模式与应用场景
Explanation 2 of redis database (redis high availability, persistence and performance management)
Codejock Suite Pro v20. three
Cookie&Session
为啥禁用外键约束
Neodynamic Barcode Professional for WPF V11.0
Application of Bloom filter in 100 million flow e-commerce system
单体架构系统重新架构
【AI周报】英伟达用AI设计芯片;不完美的Transformer要克服自注意力的理论缺陷
随机推荐
Today's sleep quality record 76 points
考试考试自用
激活函数的优缺点和选择
深度学习调参的技巧
时序模型:门控循环单元网络(GRU)
How to test mobile app?
Rsync + inotify remote synchronization
什么是CNAS认证?CNAS认可的软件测评中心有哪些?
群体智能自主作业智慧农场项目启动及实施方案论证会议
MySQL Cluster Mode and application scenario
s16.基于镜像仓库一键安装containerd脚本
pgpool-II 4.3 中文手册 - 入门教程
Redis主从复制过程
Independent operation smart farm Innovation Forum
What role does the software performance test report play? How much is the third-party test report charged?
Multitimer V2 reconstruction version | an infinitely scalable software timer
电脑怎么重装系统后显示器没有信号了
Pytorch中named_parameters、named_children、named_modules函数
Squid agent
北京某信护网蓝队面试题目