Tag name:Duplicates

[LeetCode Summary] Remove Duplicates

02/19/2014 / No Comments

先看最简单的Remove Element:
Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
这里需要理解的是给的是数组,所以新长度以后的元素都不用管了,例如给[1,2,3,4,5]要remove 3,那么结果只要是[1,2,4,5,x],并且返回新长度4就行,x是什么并不重要

下面是Remove Duplicates From 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 in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

然后变形成可以允许duplicate出现2次,把超过2次的删掉,这个也非常简单,这回用multiset
Follow up for “Remove Duplicates”:
What if duplicates are allowed at most twice?

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

Your function should return length = 5, and A is now [1,1,2,2,3].

下面看看链表,由于题目都是单链表,所以删除某一个元素需要指向该元素前一个元素的指针,这样的话头节点就比较蛋疼了,解决方法是自己定义一个头节点,使其next等于原来的头节点,这样的话原来的头节点就跟普通节点一样的操作了。
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

最后这题是要求一旦有duplicates,就删掉所有的instance,我的办法是用两个set,然后对链表扫两遍,好像有点耗时间又有点耗空间,待改进
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.