How to find missing and repeated elements at the same time

labuladong, 2020-11-11 21:02:19
missing repeated elements time


After reading this article , You can go and get the following questions :

645. The wrong set

-----------

Let's talk about a simple but ingenious question today , Looking for missing and repeating elements . A previous article 「 Look for missing elements 」 I've also written about similar questions , But the technique used in this and last question is different .

This is a LeetCode 645 topic , Let me describe the subject :

Give a length of N Array of nums, It was supposed to be [1..N] this N Elements , disorder . But now there are some mistakes ,nums One of the elements in is repeated , It also leads to the loss of another element . Please write an algorithm , find nums Duplicate and missing elements in .

// Return two numbers , Namely {dup, missing}
vector<int> findErrorNums(vector<int>& nums);

Like input :nums = [1,2,2,4], The algorithm returns [2,3].

It's easy to solve this problem , First traverse the array once , Use a hash table to record the number of times each number appears , And then go through it once [1..N], Look at the repetition of that element , That element doesn't appear , Just OK 了 .

But the problem is , This normal solution requires a hash table , That is to say O(N) Spatial complexity of . You see the conditions given by the topic are so clever , stay [1..N] There is just one repetition in a few numbers in , One missing , When things go out of whack, they will , Right .

O(N) The time complexity of traversing array is unavoidable , So we can figure out how to reduce the space complexity , Can I O(1) Find repetitive and authentic elements under the spatial complexity of ?

PS: I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .

Thought analysis

The characteristic of this problem is , Each element has a certain correspondence with the array index .

We are now transforming ourselves into problems , For the time being nums The element in becomes [0..N-1], In this way, each element corresponds exactly to an array index , This makes it easier to understand .

if nums Duplicate and missing elements are not present in , Then each element corresponds to a unique index value , Right ?

The problem now is , There's a repetition of an element , And it also causes an element to be missing , What will happen to this ? Will result in two elements corresponding to the same index , And there will be an index with no element corresponding to the past .

that , If I can do something , Find the index for this duplicate , Is that the duplicate element found ? Find the index without element , It's just that we found the missing element ?

that , How to determine how many elements of an index correspond without using extra space ? That's what makes this problem wonderful :

By making the element corresponding to each index negative , To indicate that the index has been mapped once

If there's a repeating element 4, The intuitive result is , Indexes 4 The corresponding element is already negative :

For missing elements 3, The intuitive result is , Indexes 3 The corresponding element is a positive number :

For this phenomenon , We can translate it into code :

vector<int> findErrorNums(vector<int>& nums) {
int n = nums.size();
int dup = -1;
for (int i = 0; i < n; i++) {
int index = abs(nums[i]);
// nums[index] Less than 0 Repeat visit
if (nums[index] < 0)
dup = abs(nums[i]);
else
nums[index] *= -1;
}
int missing = -1;
for (int i = 0; i < n; i++)
// nums[i] Greater than 0 It means that you have not visited
if (nums[i] > 0)
missing = i;
return {dup, missing};
}

PS: I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .

This problem has been basically solved , Don't forget that we just made it easy to analyze , Suppose the element is [0..N-1], But the question is [1..N], So you can get the answer to the original question by simply modifying two places :

vector<int> findErrorNums(vector<int>& nums) {
int n = nums.size();
int dup = -1;
for (int i = 0; i < n; i++) {
// Now the elements are from 1 At the beginning
int index = abs(nums[i]) - 1;
if (nums[index] < 0)
dup = abs(nums[i]);
else
nums[index] *= -1;
}
int missing = -1;
for (int i = 0; i < n; i++)
if (nums[i] > 0)
// Convert index to element
missing = i + 1;
return {dup, missing};
}

Actually , Elements from 1 It makes sense at first , It must also start with a non-zero number . Because if the element comes from 0 Start , that 0 The opposite of the number is itself , So if the numbers 0 There is repetition or missing , The algorithm can't judge 0 Have you ever been interviewed . Our previous hypothesis is just to simplify the topic , Easier to understand .

The final summary

For this kind of array problem , The key point is that elements and indexes appear in pairs , The common method is to sort 、 Exclusive or 、 mapping .

The idea of mapping is what we just analyzed , Map each index and element to , A sign is used to record whether an element is mapped .

The way to sort is also very good to understand , For this question , Imagine if the elements were sorted from small to large , If the corresponding elements of the index do not match , You can find the duplicate and missing elements .

XOR operations are also common , Because of the XOR nature a ^ a = 0, a ^ 0 = a, If you are either an index or an element at the same time , You can eliminate pairs of indexes and elements , What is left is a repeating or missing element . You can look at the previous article 「 Look for missing elements 」, This method has been introduced .

_____________

my Online e-books Yes 100 Original articles , Hands with brushes 200 Daoli is the subject , Recommended collection ! Corresponding GitHub Algorithm Repository We've got it 70k star, Welcome to mark star !

版权声明
本文为[labuladong,]所创,转载请带上原文链接,感谢

  1. [front end -- JavaScript] knowledge point (IV) -- memory leakage in the project (I)
  2. This mechanism in JS
  3. Vue 3.0 source code learning 1 --- rendering process of components
  4. Learning the realization of canvas and simple drawing
  5. gin里获取http请求过来的参数
  6. vue3的新特性
  7. Get the parameters from HTTP request in gin
  8. New features of vue3
  9. vue-cli 引入腾讯地图(最新 api,rocketmq原理面试
  10. Vue 学习笔记(3,免费Java高级工程师学习资源
  11. Vue 学习笔记(2,Java编程视频教程
  12. Vue cli introduces Tencent maps (the latest API, rocketmq)
  13. Vue learning notes (3, free Java senior engineer learning resources)
  14. Vue learning notes (2, Java programming video tutorial)
  15. 【Vue】—props属性
  16. 【Vue】—创建组件
  17. [Vue] - props attribute
  18. [Vue] - create component
  19. 浅谈vue响应式原理及发布订阅模式和观察者模式
  20. On Vue responsive principle, publish subscribe mode and observer mode
  21. 浅谈vue响应式原理及发布订阅模式和观察者模式
  22. On Vue responsive principle, publish subscribe mode and observer mode
  23. Xiaobai can understand it. It only takes 4 steps to solve the problem of Vue keep alive cache component
  24. Publish, subscribe and observer of design patterns
  25. Summary of common content added in ES6 + (II)
  26. No.8 Vue element admin learning (III) vuex learning and login method analysis
  27. Write a mini webpack project construction tool
  28. Shopping cart (front-end static page preparation)
  29. Introduction to the fluent platform
  30. Webpack5 cache
  31. The difference between drop-down box select option and datalist
  32. CSS review (III)
  33. Node.js学习笔记【七】
  34. Node.js learning notes [VII]
  35. Vue Router根据后台数据加载不同的组件(思考-&gt;实现-&gt;不止于实现)
  36. Vue router loads different components according to background data (thinking - & gt; Implementation - & gt; (more than implementation)
  37. 【JQuery框架,Java编程教程视频下载
  38. [jQuery framework, Java programming tutorial video download
  39. Vue Router根据后台数据加载不同的组件(思考-&gt;实现-&gt;不止于实现)
  40. Vue router loads different components according to background data (thinking - & gt; Implementation - & gt; (more than implementation)
  41. 【Vue,阿里P8大佬亲自教你
  42. 【Vue基础知识总结 5,字节跳动算法工程师面试经验
  43. [Vue, Ali P8 teaches you personally
  44. [Vue basic knowledge summary 5. Interview experience of byte beating Algorithm Engineer
  45. 【问题记录】- 谷歌浏览器 Html生成PDF
  46. [problem record] - PDF generated by Google browser HTML
  47. 【问题记录】- 谷歌浏览器 Html生成PDF
  48. [problem record] - PDF generated by Google browser HTML
  49. 【JavaScript】查漏补缺 —数组中reduce()方法
  50. [JavaScript] leak checking and defect filling - reduce() method in array
  51. 【重识 HTML (3),350道Java面试真题分享
  52. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  53. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  54. [re recognize HTML (3) and share 350 real Java interview questions
  55. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  56. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  57. 【重识 HTML ,nginx面试题阿里
  58. 【重识 HTML (4),ELK原来这么简单
  59. [re recognize HTML, nginx interview questions]
  60. [re recognize HTML (4). Elk is so simple