细语呢喃

技术改变生活

0%

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++ 

1
2
3
4
5
6
7
8
9
10
11
12
class 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
12
class 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
14
class 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
19
class 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
12
class 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
13
class 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
19
class 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
12
class 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
28
class 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
17
class 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/

请我喝杯咖啡吧~