How to find missing elements

labuladong, 2020-11-11 21:02:16
missing elements


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

448. Find all the missing numbers in the array

-----------

I've also written a few interesting intelligence questions before , Let's talk about another clever topic today .

The topic is very simple :

Give a length of n Array of , Its index should be in [0,n), But now you have to put it in n + 1 Elements [0,n], So there must be one element that can't hold it , Please find out the missing element .

The problem is not difficult , It should be easy for us to think of , Put this array in order , And then go through it , Isn't it easy to find the missing element ?

Or say , By virtue of the characteristics of data structures , Use one HashSet Save all the numbers in the array , Re traversal [0,n] Number between , Go to HashSet Query in , It's also easy to find out the missing element .

The time complexity of sorting solution is O(NlogN),HashSet The time complexity of the solution is O(N), But it needs to be O(N) Space complexity storage of HashSet.

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 .

The third method is bit operation .

For exclusive or operations (^), We know it has a special property : A number is XOR with itself, and the result is 0, A number and 0 Do XOR or itself .

And XOR operations satisfy the laws of exchange and union , in other words :

2 ^ 3 ^ 2 = 3 ^ (2 ^ 2) = 3 ^ 0 = 3

The missing element can be figured out by these properties . for instance nums = [0,3,1,4]

For ease of understanding , Let's assume that we fill in the index first , Then make each element correspond to its own equivalent index :

After doing so , You can find that in addition to the missing elements , All the indexes and elements form a pair , Now, if you put this single index 2 To find out , And you find the missing element .

How to find this single figure , Just XOR all the elements and indexes , The numbers in pairs will disappear into 0, Only this single element is left , We have achieved our goal .

int missingNumber(int[] nums) {
int n = nums.length;
int res = 0;
// First XOR with the new index
res ^= n;
// And other elements 、 Index XOR
for (int i = 0; i < n; i++)
res ^= i ^ nums[i];
return res;
}

Because the XOR operation satisfies the commutative law and the associative law , So it's always possible to eliminate pairs of numbers , Leaving the missing element .

thus , Time complexity O(N), Spatial complexity O(1), We've reached the best , Should we just go back home ?

If you think so , It shows that we are too poisoned by the algorithm , As we learn more and more knowledge , On the contrary, it is easy to fall into the fixed pattern of thinking , There is actually a very simple solution to this problem : The summation formula of the sequence of equal differences .

The meaning of the title can be understood in this way : Now there's an arithmetic sequence 0, 1, 2,..., n, One of the missing numbers , Please find it out . So this number is not sum(0,1,..n) - sum(nums) Well ?

int missingNumber(int[] nums) {
int n = nums.length;
// The formula :( First item + Last item ) * Number of items / 2
int expect = (0 + n) * (n + 1) / 2;
int sum = 0;
for (int x : nums)
sum += x;
return expect - sum;

You see , This solution should be the simplest , But tell the truth. , I didn't think of this solution myself , And I went to ask some big guys , They didn't think of the simplest idea either . contrary , If you ask a junior high school student , He may soon be able to think of .

It's done , Should we just go back home ?

If you think so , It shows that our control of the details is almost perfect . In calculating with the summation formula expect when , You think about it The integer overflow Do you ? If the result of multiplication is too large to cause overflow , Then the result must be wrong .

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 .

Our idea just now is to add both sums and subtract them , To avoid spillage , Just sum and subtract at the same time . It's very similar to the idea of bit operation , Still assuming nums = [0,3,1,4], First fill in an index and then match the element with the index :

We let each index subtract its corresponding element , And add up the results of subtraction , It's the missing element ?

public int missingNumber(int[] nums) {
int n = nums.length;
int res = 0;
// New index
res += n - 0;
// Add up the difference between the index and the element
for (int i = 0; i < n; i++)
res += i - nums[i];
return res;
}

Because addition and subtraction satisfy the law of exchange and law of combination , So it's always possible to eliminate pairs of numbers , Leaving the missing element .

So far, this algorithm has gone through nine twists and eighteen turns , Finally, there is no more pit .

_____________

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