当前位置:网站首页>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
边栏推荐
- Upgrade MySQL 5.1 to 5.68
- 推荐搜索 常用评价指标
- PHP function
- Why disable foreign key constraints
- 如果conda找不到想要安装的库怎么办PackagesNotFoundError: The following packages are not available from current
- How to test mobile app?
- 今日睡眠质量记录76分
- PHP operators
- PHP PDO ODBC loads files from one folder into the blob column of MySQL database and downloads the blob column to another folder
- Mysql database explanation (10)
猜你喜欢
随机推荐
APISIX jwt-auth 插件存在错误响应中泄露信息的风险公告(CVE-2022-29266)
时序模型:门控循环单元网络(GRU)
小程序知识点积累
Special analysis of China's digital technology in 2022
Go语言条件,循环,函数
怎么看基金是不是reits,通过银行购买基金安全吗
Mobile finance (for personal use)
Explanation of redis database (I)
Connect PHP to MySQL via PDO ODBC
2022年中国数字科技专题分析
字符串排序
【递归之数的拆分】n分k,限定范围的拆分
Cookie&Session
什么是CNAS认证?CNAS认可的软件测评中心有哪些?
Neodynamic Barcode Professional for WPF V11. 0
ICE -- 源码分析
el-tree实现只显示某一级复选框且单选
电脑怎么重装系统后显示器没有信号了
Mumu, go all the way
幂等性的处理