How to remove duplicate elements of ordered array

labuladong 2020-11-12 22:23:52
remove duplicate elements ordered array


How to remove duplicate elements from ordered arrays

After reading this article , You've not only learned the algorithmic routine , You can also drop in LeetCode Take the following questions :

26. Delete duplicates in sort array

83. Delete duplicate elements from the sort list

27. Remove elements

283. Move zero

-----------

We know that for arrays , Insert at tail 、 It is more efficient to delete elements , The time complexity is O(1), But if you insert it in the middle or at the beginning 、 Remove elements , It's about moving data , The time complexity is O(N), Low efficiency .

So the last article O(1) Time deletion / Find any element in the array I just talked about a technique , Exchange the element to be deleted to the last one , And then delete it , You can avoid data movement .

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 .

Ordered array / The chain watch is weightless

Let's talk about how to de duplicate an ordered array , Let's look at the title first :

The function signature is as follows :

int removeDuplicates(int[] nums);

obviously , Because the array has been sorted , So the repeating elements must be connected , It's not hard to find them , But if every duplicate element is found, delete it immediately , Is to delete in the middle of the array , The whole time complexity is going to be O(N^2).

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 .

Briefly explain what it means to modify in place :

If it wasn't revised in place , We directly new One int[] Array , Put the de duplicated elements into the new array , Then return the new array .

But delete it in place , We are not allowed to new New array , You can only operate on the original array , And then return a length , In this way, we can get the returned length and the original array to find out what elements we have after de duplication .

This requirement is very common in array related algorithmic problems , The general solution is what we mentioned earlier Double pointer technique The fast and slow pointer technique in .

Let's slow the pointer slow Walk in the back , Quick pointer fast Go ahead and find the way , Find an element that doesn't repeat and tell slow And let slow Take a step forward . So when fast Pointer traverses the entire array nums after ,nums[0..slow] It's not repeating elements .

int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
slow++;
// maintain nums[0..slow] No repetition
nums[slow] = nums[fast];
}
fast++;
}
// The length of the array is index + 1
return slow + 1;
}

Take a look at the process of algorithm execution :

Just expand it a little bit , If I give you an ordered list , How to remove heavy ? It's a force lock 83 topic , In fact, as like as two peas, the weight is exactly the same , The only difference is that it turns an array assignment into an operation pointer :

ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
ListNode slow = head, fast = head;
while (fast != null) {
if (fast.val != slow.val) {
// nums[slow] = nums[fast];
slow.next = fast;
// slow++;
slow = slow.next;
}
// fast++
fast = fast.next;
}
// Disconnect from the following repeating elements
slow.next = null;
return head;
}

Remove elements

It's a force lock 27 topic , Look at the title :

The function signature is as follows :

int removeElement(int[] nums, int val);

The title asks us to put nums All values in are val Delete the element in place , Still need to use Double pointer technique The speed pointer in :

If fast Encounter elements that need to be removed , Then skip directly , Or tell slow The pointer , And let slow Take a step forward .

This is exactly the same as the solution to the array de duplication problem mentioned earlier , Don't draw GIF 了 , Look directly at the code :

int removeElement(int[] nums, int val) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}

Note that there is an important difference between this method and the solution of ordered array de duplication , We are here to give nums[slow] Assign a value and then give it to slow++, This ensures nums[0..slow-1] Does not contain a value of val The elements of the , The final result is the length of the array slow.

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 .

Move zero

It's a force lock 283 topic , Let me describe the topic :

I'll give you an array nums, Would you please Modify in place , Set all values in the array as 0 To the end of the array , The function signature is as follows :

void moveZeroes(int[] nums);

For example, I'll give you input nums = [0,1,4,0,2], Your algorithm has no return value , But I will nums Change the array in place to [1,4,2,0,0].

A couple of previous topics , Do you have the answer ?

Let's put all of them together 0 Move to the last , It's like removing nums All in 0, Then assign the following elements to 0 that will do .

So we can reuse the previous question removeElement function :

void moveZeroes(int[] nums) {
// Remove nums All in 0
// Return to remove 0 The length of the array after
int p = removeElement(nums, 0);
// take p All subsequent elements are assigned the value of 0
for (; p < nums.length; p++) {
nums[p] = 0;
}
}
// See code implementation above
int removeElement(int[] nums, int val);

thus , The four way 「 Modify in place 」 And that's all , In fact, the core is still fast and slow pointer skills , Have you learned ?

Related to recommend :

_____________

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