当前位置:网站首页>Duplicate numbers in array
Duplicate numbers in array
2022-07-25 23:24:00 【Longqi Liuhe】
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 .
Formula example 1 :
Input :
[2, 3, 1, 0, 2, 5, 3]
Output :
2 or 3
analysis :
You can use sorting , After sorting the array , Compare adjacent elements in turn , See if they are equal , Equal to return to .
You can also use hash table , Store the elements in the array into the hash table , When this element is found in the hash table when saving, it returns .
Want to find the optimal solution , Be good at using the conditions in the diagram , The title says that the array length is n And all the numbers in the array are 0-n-1 Within the scope of , You can use the subscript method , Make the element equal to its corresponding subscript by constantly exchanging elements , This makes it easy to judge repeated elements . The time complexity of the optimal solution O(n), The space complexity is O(1).
Code :
// The subscript method
public int findRepeatNumber3(int[] nums) {
for (int i = 0; i < nums.length; i++) {
// use while After the exchange , The element in this position is still not in the correct position
while (i != nums[i]){
if (nums[i] == nums[nums[i]]){
// repeat
return nums[i];
}
int k = nums[nums[i]];
nums[nums[i]] = nums[i];
nums[i] = k;
}
}
return -1;
}

边栏推荐
- Tencent map API request source is not authorized, this request source domain name
- anaconda安装教程环境变量(如何配置环境变量)
- ETL工具(数据同步) 二
- idea设置get、set模板解决boolean类型字段的命名问题
- Take away applet with main version of traffic / repair to add main access function of traffic
- Recommended system - an embedded learning framework for numerical features in CTR prediction
- 【微信小程序】页面导航
- npm+模块加载机制
- Drive board network cable directly connected to computer shared network configuration
- 行云管家V6.5.1/2/3系列版本发布:数据库OpenAPI能力持续强化
猜你喜欢

XxE & XML external entity injection utilization and bypass

Family relationship calculator wechat applet source code

npm+模块加载机制

学习探索-3d轮播卡片

Several commonly used traversal methods

Network Security Learning notes-1 file upload

WordPress removes the website publishing time

Firewall command simple operation

@Import

通用分页功能
随机推荐
Which securities firm is the best and safest for beginners to open an account
ETL工具(数据同步) 二
TS function
OASYS system of code audit
Cuteone: a onedrive multi network disk mounting program / with member / synchronization and other functions
物理防火墙是什么?有什么作用?
自定义mvc原理
E-commerce RPA, a magic weapon to promote easy entry
Explain in detail the addition (+) operation in JS, basic data type addition, reference data type addition, and the underlying operation rules, [] + {}, {} + []
Servlet overview
Discuz atmosphere game style template / imitation lol hero League game DZ game template GBK
学习探索-波浪
TS class
学习探索-3d轮播卡片
Recommended system - an embedded learning framework for numerical features in CTR prediction
Classes and objects (2) (6 default member functions)
CTS测试方法「建议收藏」
MES系统设备管理概述(下)
Unity 使用宏
策略模式_