# 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 in place with constant memory.

For example, Given input array 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.

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.empty())
return 0;
int i=0,new_len=0;
for(i=1;i<nums.size();i++){
if(nums[i]!=nums[new_len])
nums[++new_len]=nums[i];
}
return new_len+1;
}
};


class Solution {
public:
int removeDuplicates(vector<int>& nums) {
return distance(nums.begin(),unique(nums.begin(),nums.end()));
}
};


# 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.

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size()<3)
return nums.size();
int new_len=1,size=nums.size(),i=0;
for(i=2;i<size;i++){
if(nums[i]!=nums[new_len-1])
nums[++new_len]=nums[i];
}
return new_len+1;
}
};


# 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.

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
while(pmove){
qmove=pmove;
while(qmove->next){
if(pmove->val==qmove->next->val){
tmp=qmove->next;
qmove->next=tmp->next;
free(tmp);
}
else
qmove=qmove->next;
}
pmove=pmove->next;
}
}
};


# 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.

1.发现当前元素和后继元素相等: 此时我们只需要按删除链表中某一元素的方法，删去后一元素即可，同时令标记值为true

2.标记值为true 此时就需要用我们的pre指针，借助其完成删除重复元素集合的首元素，删除之后，令cur指向pre的后继元素，同时令标记值为false

3.其余情况 pre，cur指针后移即可

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
struct ListNode dummy(0);
bool duplicate=false;
while(cur){
if(cur->next&&cur->val==cur->next->val){
tmp=cur->next;
cur->next=tmp->next;
free(tmp);
duplicate=true;
}
else if(duplicate){
pre->next=cur->next;
free(cur);
cur=pre->next;
duplicate=false;
}
else{
pre=cur;
cur=cur->next;
}
}
}
};



### 学籍管理系统文档

#### 北邮教务系统评教脚本

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017