- 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++ 1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.empty()) return 0;
int len = 1;
for(int i = 1; i < nums.size(); ++i){
if(nums[i] != nums[i - 1])
nums[len++] = nums[i];
}
return len;
}
};
Python 1
2
3
4
5
6
7
8
9
10
11
12class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
j = 1 if nums else 0
for i in range(1, len(nums)):
if nums[i] != nums[i - 1]:
nums[j] = nums[i]
j += 1
return j
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 >＝２说明有两个元素，应在写一次。复杂度为O(n)
C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() <= 2) return nums.size();
int len = 0;
for(int i = 0, j = 1; i < nums.size(); i = j++){
while(j < nums.size() && nums[i] == nums[j]) ++j;
nums[len++] = nums[i];
if(j - i >= 2)
nums[len++] = nums[i];
}
return len;
}
};
Python 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <= 2: return len(nums)
k = 0 # new length
i, j = 0, 1
while i < len(nums):
while j < len(nums) and nums[i] == nums[j]:
j += 1
nums[k] = nums[i]
k += 1
if j - i >= 2:
nums[k] = nums[i]
k += 1
i, j = j, j + 1
return k
方法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++ 1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() <= 2) return nums.size();
int len = 2;
for(int i = 2; i < nums.size(); ++i){
if(nums[i] != nums[len - 2])
nums[len++] = nums[i];
}
return len;
}
};
Python 1
2
3
4
5
6
7
8
9
10
11
12
13class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <= 2: return len(nums)
k = 2
for i in range(2, len(nums)):
if nums[i] != nums[k - 2]:
nums[k] = nums[i]
k += 1
return k
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++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head) return head;
ListNode *p = head, *q = head->next, *t = nullptr;
while(q){
if(p->val == q->val){
t = q;
p->next = q = q->next;
delete t;
}
else{
p = q;
q = q->next;
}
}
return head;
}
};
Python 1
2
3
4
5
6
7
8
9
10
11
12class Solution:
# @param head, a ListNode
# @return a ListNode
def deleteDuplicates(self, head):
p, q = ListNode(-1), head
p.next, head = head, p
while q:
while q.next and q.next.val == q.val:
q = q.next
p.next, p = q, q
if q: q = q.next
return head.next
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++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head) return head;
ListNode *dummy = new ListNode(-1);
dummy->next = head;
ListNode *p = dummy, *q = head, *temp = nullptr;
while (q) {
while (q->next && q->next->val == q->val) q = q->next;
if (p->next == q) p = q;
else { //delete[p->next, q]
for (ListNode *it = p->next; it != q; ) {
temp = it;
it = it->next;
delete temp;
}
p->next = q->next;
delete q;
}
q = p->next;
}
head = dummy->next;
delete dummy;
return head;
}
};
Python 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
p, q = ListNode(-1), head
p.next, head = head, p
while q:
while q.next and q.next.val == q.val:
q = q.next
if p.next == q:
p = q
else:
p.next = q.next
q = p.next
return head.next
本文是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/
