当前位置:网站首页>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
边栏推荐
- 一刷313-剑指 Offer 06. 从尾到头打印链表(e)
- 电脑怎么重装系统后显示器没有信号了
- PHP PDO ODBC loads files from one folder into the blob column of MySQL database and downloads the blob column to another folder
- Neodynamic Barcode Professional for WPF V11.0
- What are the mobile app software testing tools? Sharing of third-party software evaluation
- Deeply learn the skills of parameter adjustment
- Codejock Suite Pro v20. three
- 今日睡眠质量记录76分
- Openstack theoretical knowledge
- 字符串最后一个单词的长度
猜你喜欢
随机推荐
码住收藏▏软件测试报告模板范文来了
G007-HWY-CC-ESTOR-03 华为 Dorado V6 存储仿真器搭建
Demonstration meeting on startup and implementation scheme of swarm intelligence autonomous operation smart farm project
Summary of interfaces for JDBC and servlet to write CRUD
Mysql database explanation (8)
Redis主从复制过程
推荐搜索 常用评价指标
Knn,Kmeans和GMM
Do keyword search, duplicate keyword search, or do not match
Connect PHP to MSSQL via PDO ODBC
GFS distributed file system (Theory)
KNN, kmeans and GMM
G007-hwy-cc-estor-03 Huawei Dorado V6 storage simulator construction
el-tree实现只显示某一级复选框且单选
utils.DeprecatedIn35 因升级可能取消,该如何办
Go语言条件,循环,函数
Advantages, disadvantages and selection of activation function
Go并发和通道
一刷314-剑指 Offer 09. 用两个栈实现队列(e)
网站压测工具Apache-ab,webbench,Apache-Jemeter