当前位置:网站首页>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;
}

边栏推荐
- Explain in detail the addition (+) operation in JS, basic data type addition, reference data type addition, and the underlying operation rules, [] + {}, {} + []
- idea设置get、set模板解决boolean类型字段的命名问题
- Mongodb update operator (modifier)
- Take away applet with main version of traffic / repair to add main access function of traffic
- Classes and objects (3)
- Summary of common PHP functions
- Week 2: convolutional neural network
- Implementation of mesh parameterized least squares conformal maps (3D mesh mapping to 2D plane)
- firewall 命令简单操作
- Mongodb query and projection operators
猜你喜欢

向下扎根,向上生长,探寻华为云AI的“根”力量

赋能合作伙伴,亚马逊云科技如何落地“扶上马,送一程”?

@Import

Firewall command simple operation

通用分页功能

学习探索-波浪

Discuz atmosphere game style template / imitation lol hero League game DZ game template GBK

Analysis of the influence of ESM direction finding error on positioning error

Multimodal deep multi modal sets

Apple CMS V10 template /mxone Pro adaptive film and television website template
随机推荐
数组中重复的数字
Unity 使用宏
Data broker understanding
The small icon of notification setting shows a small square
About using NPM command under the terminal, the installation error problem is solved (my own experience)
Analysis of direction finding error of multi baseline interferometer system
TS function
Expression of directional signal -- complex exponential signal
Secure code warrior learning record (III)
XXE&XML-外部实体注入-利用和绕过
PHP binary array is sorted by a field in it
Summary of common PHP functions
Unity uses macros
Vscode shortcut key: collapse and expand code
Simulink learning notes (III) - Simulink automatic code generation (II) "suggestions collection"
Rendering, filtering (filtering) and sorting of lists
How to set pseudo static for WordPress fixed links
Mongodb features, differences with MySQL, and application scenarios
Analysis of the influence of ESM direction finding error on positioning error
JS get the current date and time