当前位置:网站首页>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
边栏推荐
- Code live collection ▏ software test report template Fan Wen is here
- 自动化测试框架常见类型▏自动化测试就交给软件测评机构
- Common types of automated testing framework ▏ automated testing is handed over to software evaluation institutions
- Codejock Suite Pro v20. three
- Go语言条件,循环,函数
- Upgrade MySQL 5.1 to 5.67
- Openstack command operation
- Squid agent
- Cookie&Session
- Mysql database explanation (8)
猜你喜欢
Why disable foreign key constraints
Basic concepts of website construction and management
c语言---字符串+内存函数
多生成树MSTP的配置
G007-hwy-cc-estor-03 Huawei Dorado V6 storage simulator construction
WPS品牌再升级专注国内,另两款国产软件低调出国门,却遭禁令
Single architecture system re architecture
电脑怎么重装系统后显示器没有信号了
自主作业智慧农场创新论坛
Mysql database explanation (10)
随机推荐
Mysql database explanation (VII)
WPS品牌再升级专注国内,另两款国产软件低调出国门,却遭禁令
考试考试自用
PHP function
PHP PDO ODBC将一个文件夹的文件装载到MySQL数据库BLOB列,并将BLOB列下载到另一个文件夹
电脑怎么重装系统后显示器没有信号了
Elk installation
Explanation of redis database (I)
计算某字符出现次数
多生成树MSTP的配置
Leetcode学习计划之动态规划入门day3(198,213,740)
一刷313-剑指 Offer 06. 从尾到头打印链表(e)
一刷312-简单重复set-剑指 Offer 03. 数组中重复的数字(e)
一刷314-剑指 Offer 09. 用两个栈实现队列(e)
Machine learning - logistic regression
Redis主从复制过程
PHP classes and objects
幂等性的处理
JVM-第2章-类加载子系统(Class Loader Subsystem)
MySQL Cluster Mode and application scenario