leetcode Remove Duplicates 整理

  • 26. Remove Duplicates from Sorted Array
  • 80. Remove Duplicates from Sorted Array II
  • 82. Remove Duplicates from Sorted List II
  • 83. Remove Duplicates from Sorted List

26. Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn’t matter what you leave beyond the new length.

题目地址:leetcode Remove Duplicates from Sorted Array

题目大意:给定排好序的数组,去除其重复元素并返回去除后长度。

思路:

用len记录新的长度。当nums[i] != nums[i – 1]的时候,说明不是重复元素。

C++

Python

 

 


 

80. Remove Duplicates from Sorted Array II

Follow up for “Remove Duplicates”:
What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn’t matter what you leave beyond the new length.

题目地址:leetcode Remove Duplicates from Sorted Array II

题目大意:给定排好序的数组,去除其重复元素(每个元素最多重复两次)并返回去除后长度。

思路:

方法1

i指向当前元素的第一个位置,j指向下一个元素第一位置。 j-i >=2说明有两个元素,应在写一次。复杂度为O(n)

C++

 Python

方法2

类似第26题的做法,

用len记录新数组长度,在遍历过程中,len就是指向放置新元素的位置。

则若nums[i] != nums[len – 2], 说明应该存放,因为新数组中不超过2个值为nums[i]的元素。

注意这里应写len – 2而不是i – 2,因为i – 2可能被覆盖。就是样例的[1,1,1,2,2,3]

C++

Python

 


 

83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

题目地址:leetcode Remove Duplicates from Sorted List

题目大意:给定排好序的链表,对于重复元素仅保留一个。

思路:看代码吧

C++

 Python

 


 

82. Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

题目地址:leetcode Remove Duplicates from Sorted List II

题目大意:给定排好序的链表,取出所有重复元素。

思路:和上面一题(83)区别在于不保留重复元素。

  • 当q==p->next说明无重复元素,应该p=q
  • 否则,p->next=q->next

C++

python

 

本文是leetcode如下的题解

  • 26. Remove Duplicates from Sorted Array
  • 80. Remove Duplicates from Sorted Array II
  • 82. Remove Duplicates from Sorted List II
  • 83. Remove Duplicates from Sorted List

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Remove Duplicates 整理
本文地址:https://www.hrwhisper.me/leetcode-remove-duplicates-from-sorted-array-or-remove-duplicates-from-sorted-list/

您的支持将鼓励我继续创作!

Leetcode . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *