有人要36寸的神器二代么？价格不贵，我买错了 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Living

有人要36寸的神器二代么？价格不贵，我买错了

有人要36寸的神器二代么？价格不贵，我买错了# Living

n*g2012-08-26 07:08

1 楼

请教大家，下面是我自己写的一个移除已排列好的数组中的重复袁福的代码，但我对时
间复杂度的概念比较模糊，能否指教一下？？
需不需要按最坏和平均情况来分析，我一直搞不懂..
int removeDuplicateSortedArray(int A[], int n)//leetcode all passed
{
int duplicate=0,prev=0,cur=prev+1,len,newPosit;

if(n==1)//一个元素就不考虑了
return 1;
if(n==0) //一个元素都没有更不考虑
return 0;
for(prev=0;prev{
cur = prev+1;
if(A[prev]==A[cur])//找到相同元素
{
//直接把相同元素后面的全幅往前移一格
for(newPosit=cur;newPosit{
A[newPosit]=A[newPosit+1];
}
duplicate++; //重复数加一
prev--; //循环退一格，看看还有没有重复
}
}
return n-duplicate;
}
谢谢了！！！！

a*s2012-08-26 07:08

2 楼

PD Nov 2011
打电话过去，说some one pulled out and started to review your file on May 6th
which was yesterday, can't tell how long it will take.
四月份的时候交回去了体检RFE。TSC的。
请问：这样一般还需要等多少时间得到回复；另外这是不是意味着relink自动完成不需
要再interfile了？
谢谢！

J*92012-08-26 07:08

3 楼

http://www.mitbbs.com/article_t/FleaMarket/33417347.html

n*r2012-08-26 07:08

4 楼

你这个是O(N^3)的时间复杂度！删除重复元素，若是已排序数组，应该做到O(n)，未排
序数组，应该是O(N^2).
前两个if完全可以合成一个if，其实可以完全不需要这个if。
在处理元素a[i]时，从i+1开始查找相同的元素，找到后就把后面的所有元素前移。这
个地方不科学！比方{1,1,1,1,1},既然是已排序数组，为什么不一直跳过重复元素呢？

a*s2012-08-26 07:08

5 楼

版主版花能看一下吗？谢谢啦！

J*92012-08-26 07:08

6 楼

up~

n*g2012-08-26 07:08

7 楼

哦，我看到了O（N）的算法，确实应该那样。能不能解释一下为什么之前那个是O（N^3
)呢？

【在 n****r 的大作中提到】

: 你这个是O(N^3)的时间复杂度！删除重复元素，若是已排序数组，应该做到O(n)，未排
: 序数组，应该是O(N^2).
: 前两个if完全可以合成一个if，其实可以完全不需要这个if。
: 在处理元素a[i]时，从i+1开始查找相同的元素，找到后就把后面的所有元素前移。这
: 个地方不科学！比方{1,1,1,1,1},既然是已排序数组，为什么不一直跳过重复元素呢？

d*e2012-08-26 07:08

8 楼

你这个错的吧。
"1,2,1"好像通不过。
排好序的可以用O(n) time O(1) space
没排序的用hash记录，O(n) time, O(n) space

【在 n*****g 的大作中提到】

: 请教大家，下面是我自己写的一个移除已排列好的数组中的重复袁福的代码，但我对时
: 间复杂度的概念比较模糊，能否指教一下？？
: 需不需要按最坏和平均情况来分析，我一直搞不懂..
: int removeDuplicateSortedArray(int A[], int n)//leetcode all passed
: {
: int duplicate=0,prev=0,cur=prev+1,len,newPosit;
:
: if(n==1)//一个元素就不考虑了
: return 1;
: if(n==0) //一个元素都没有更不考虑

n*g2012-08-26 07:08

9 楼

【在 d**e 的大作中提到】

: 你这个错的吧。
: "1,2,1"好像通不过。
: 排好序的可以用O(n) time O(1) space
: 没排序的用hash记录，O(n) time, O(n) space

n*r2012-08-26 07:08

10 楼

哦，忘了hash，谢谢done的提醒。没排序的用hash时间上可以做到O(n).
O(N^3)的分析
我们就拿{0,0,0,0,1,1,1,1,1}来分析
外部循环prev从左扫到右，假设你不回退prev，那么就是N
内部循环对每一个一个重复元素，将其后面的全部前移一位，那么这也是N
这已经就是O(N^2)了。
每次在重复元素处理之后回退prev指针，（那么prev就是有几个重复元素，就要回退几
次）其实相当于又在上面两个循环之间增加了一个循环来处理同一个元素的多个重复元
素的情况。O(N^3)了。