leetcode： Remove Duplicates from Sorted Array - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

leetcode： Remove Duplicates from Sorted Array

leetcode： Remove Duplicates from Sorted Array# JobHunting - 待字闺中

x*02013-03-07 08:03

1 楼

开始做leetcode，按二爷的总结，由易到难，一天两道。
今天是 remove duplicates from sorted array 1, 2
http://leetcode.com/onlinejudge#question_26
http://leetcode.com/onlinejudge#question_80
下面是我的代码：
int rightMost_of_curElem(int A[], int curElem, int ind, int n)
{
while(ind{
if(A[ind]!=curElem)
break;
++ind;
}

return --ind;
}
（1）
int remove_duplicates(int A[], int n)
{
int i=0;
int unique_num = 0;
while(i{
int cur_elem = A[i];
int pos = rightMost_of_curElem(A, cur_elem, i, n);
//cout << pos << endl;
i = pos+1;
A[unique_num++] = A[pos];
}

return unique_num;
}
（2）
int remove_duplicates(int A[], int n)
{
int i=0;
int unique_num = 0;
while(i{
int cur_elem = A[i];
int pos = rightMost_of_curElem(A, cur_elem, i, n);

if(A[pos]==A[pos-1])
{
A[unique_num++] = A[pos];
}
A[unique_num++] = A[pos];

i = pos+1;
}

return unique_num;
}
代码经过了online的测试~。如果哪位哥们有空，帮忙review代码那是最好啦~。就代
码本身提些意见。先谢谢啦。其实能一起交流那是最好了，我也很乐意提出我的意见。
就是水平太菜的话，别介意哈~

c*l2013-03-07 08:03

2 楼

public class Solution {
public int removeDuplicates(int[] A) {
if(A.length == 0) // edge case
return 0;

int len = A.length;
int curIdx = 1;
int endIdx = 0;
while(curIdx < len) {
if(A[endIdx] == A[curIdx])
curIdx++;
else
A[++endIdx] = A[curIdx++];
}
return endIdx + 1;
}
}

f*42013-03-07 08:03

3 楼

我也写了一个，1和2的做法一样
int removeDuplicates(int A[], int n) {
int uniq = (n<=1?n:2);
for (int i=2; iif (A[i] != A[uniq-1] || A[i] != A[uniq-2])
A[uniq++] = A[i];
}
return uniq;
}

【在 x*****0 的大作中提到】

: 开始做leetcode，按二爷的总结，由易到难，一天两道。
: 今天是 remove duplicates from sorted array 1, 2
: http://leetcode.com/onlinejudge#question_26
: http://leetcode.com/onlinejudge#question_80
: 下面是我的代码：
: int rightMost_of_curElem(int A[], int curElem, int ind, int n)
: {
: while(ind: {
: if(A[ind]!=curElem)

x*02013-03-07 08:03

4 楼

根据Loki的建议，重写了代码。现在将能够容忍的重复次数作为参数。如下：
int getNextElement(int *data, int len, int start, int curElem)
{
for(; (start < len) && (data[start]==curElem); start++)
{
}

return start;
}
int removeDuplicatesUtil(int *data, int len, int tolerance)
{
int count = 0;
int nextBeg = 0;
for (int curBeg = 0; curBeg < len; curBeg=nextBeg)
{
nextBeg = getNextElement(data, len, curBeg+1, data[curBeg]);
int curEnd = min(curBeg+tolerance, nextBeg);

memcpy(data+count, data+curBeg, (curEnd-curBeg)*sizeof(data[0]));
count += (curEnd-curBeg);
}

return count;
}
int removeDuplicates(int *data, int len)
{
return removeDuplicatesUtil(data, len, 1);
//return removeDuplicatesUtil(data, len, 2);
}
reference:
http://codereview.stackexchange.com/questions/23582/remove-dupl

E*U2013-03-07 08:03

5 楼

class Solution {
public:
int removeDuplicates(int A[], int n) {
if (!A || n <= 0) return 0;
int dsc = 1;
for (int i = 1; i < n; ++i)
{
if (A[i] != A[i-1])
{
A[dsc++] = A[i];
}
}
return dsc;
}
};

l*n2013-03-07 08:03

6 楼

请帮我看看我错在哪里了, 测试[1,1,1] 无返回
class Solution {
public:
int removeDuplicates(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int i=0;
int m = n; //return value
while(A[i+1] != '\0')
{
if (A[i] == A[i+1])
{
// remove current
int k=i;

while(A[k+1] != '\0')
{
A[k] = A[k+1];

k++;
}

A[k] = '\0';

m --;
}

i++;
}

return m;

}
};

E*U2013-03-07 08:03

7 楼

Remove Duplicates from Sorted Array II:
class Solution {
public:
int removeDuplicatesII(int A[], int n) {
if (!A || n <= 0) return 0;
int dsc = 1;
int dupCount = 0;
for (int i = 1; i < n; ++i)
{
if (A[i] != A[i-1])
{
A[dsc++] = A[i];
dupCount = 0;
}
else
{
++dupCount;
if (dupCount < 2)
{
A[dsc++] = A[i];
}
}
}
return dsc;
}
};