A*e
2 楼
已经是O(n)/O(1)了,怎么提交的答案在C/C++里特别慢?用了46ms,但分布图显示不到
20ms就够了,甚至还有不到10ms的。试着用equal_range跳着来,结果更慢,56ms。这
里面有啥秘诀?
class Solution {
public:
int removeDuplicates(int A[], int n) {
if (n == 0) {
return 0;
}
int dup_count = 0;
int base = A[0];
for (int i = 1; i < n; ++i) {
if (A[i] == base) {
++dup_count;
} else {
if (dup_count > 0) {
A[i - dup_count] = A[i];
}
base = A[i];
}
}
return n - dup_count;
}
};
class Solution {
public:
int removeDuplicates(int A[], int n) {
if (n == 0) {
return 0;
}
vector v(A, A + n);
int base = v[0];
int dup_count = 0;
while (true) {
auto bound = equal_range(v.begin(), v.end(), base);
dup_count += (bound.second - bound.first - 1);
if (bound.second == v.end()) {
break;
} else {
base = *bound.second;
int idx = bound.second - v.begin();
A[idx - dup_count] = A[idx];
}
}
return n - dup_count;
}
};
20ms就够了,甚至还有不到10ms的。试着用equal_range跳着来,结果更慢,56ms。这
里面有啥秘诀?
class Solution {
public:
int removeDuplicates(int A[], int n) {
if (n == 0) {
return 0;
}
int dup_count = 0;
int base = A[0];
for (int i = 1; i < n; ++i) {
if (A[i] == base) {
++dup_count;
} else {
if (dup_count > 0) {
A[i - dup_count] = A[i];
}
base = A[i];
}
}
return n - dup_count;
}
};
class Solution {
public:
int removeDuplicates(int A[], int n) {
if (n == 0) {
return 0;
}
vector
int base = v[0];
int dup_count = 0;
while (true) {
auto bound = equal_range(v.begin(), v.end(), base);
dup_count += (bound.second - bound.first - 1);
if (bound.second == v.end()) {
break;
} else {
base = *bound.second;
int idx = bound.second - v.begin();
A[idx - dup_count] = A[idx];
}
}
return n - dup_count;
}
};
S*M
3 楼
【 以下文字转载自 Fashion 讨论区 】
发信人: lemma (证明定理), 信区: Fashion
标 题: 求意见,这个撞色是不是有点过了?
发信站: BBS 未名空间站 (Mon Jun 20 18:01:30 2011, 美东)
去H&M逛了一圈,好想都买下来,我要忍住,忍住。。。。
求意见,这个撞色是不是有点过了?
发信人: lemma (证明定理), 信区: Fashion
标 题: 求意见,这个撞色是不是有点过了?
发信站: BBS 未名空间站 (Mon Jun 20 18:01:30 2011, 美东)
去H&M逛了一圈,好想都买下来,我要忍住,忍住。。。。
求意见,这个撞色是不是有点过了?
c*n
4 楼
面的时候都没有人care 到这一层吧, 即使care 他也没法查,你就不要给自己找麻烦
了。 有这功夫看看算法, design pattern, 或什么open source project 管用得多
【在 A*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 已经是O(n)/O(1)了,怎么提交的答案在C/C++里特别慢?用了46ms,但分布图显示不到
: 20ms就够了,甚至还有不到10ms的。试着用equal_range跳着来,结果更慢,56ms。这
: 里面有啥秘诀?
: class Solution {
: public:
: int removeDuplicates(int A[], int n) {
: if (n == 0) {
: return 0;
: }
: int dup_count = 0;
了。 有这功夫看看算法, design pattern, 或什么open source project 管用得多
【在 A*******e 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 已经是O(n)/O(1)了,怎么提交的答案在C/C++里特别慢?用了46ms,但分布图显示不到
: 20ms就够了,甚至还有不到10ms的。试着用equal_range跳着来,结果更慢,56ms。这
: 里面有啥秘诀?
: class Solution {
: public:
: int removeDuplicates(int A[], int n) {
: if (n == 0) {
: return 0;
: }
: int dup_count = 0;
c*e
6 楼
算法的时间复杂度,及其优化
和实际计算机上执行耗费的时间,以及优化
是两个不同层面的性能问题
你这样混到一起谈,就说不清了
同样的o(n)同样的算法同样的逻辑,我在语言和指令级别给你优化,差个100倍也不奇怪
和实际计算机上执行耗费的时间,以及优化
是两个不同层面的性能问题
你这样混到一起谈,就说不清了
同样的o(n)同样的算法同样的逻辑,我在语言和指令级别给你优化,差个100倍也不奇怪
b*5
7 楼
Oh...攒眼熟ID 奔。。。
a*l
9 楼
清秀的脸庞,正。
l*a
14 楼
你写得有点难懂啊,这么写是不是清楚点?
int write=1;
for(int read=1;read<=A.length-1;read++) {
if(A[read]!=A[write-1]) {
A[write++]=A[read];
}
}
return write;
【在 A*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 已经是O(n)/O(1)了,怎么提交的答案在C/C++里特别慢?用了46ms,但分布图显示不到
: 20ms就够了,甚至还有不到10ms的。试着用equal_range跳着来,结果更慢,56ms。这
: 里面有啥秘诀?
: class Solution {
: public:
: int removeDuplicates(int A[], int n) {
: if (n == 0) {
: return 0;
: }
: int dup_count = 0;
int write=1;
for(int read=1;read<=A.length-1;read++) {
if(A[read]!=A[write-1]) {
A[write++]=A[read];
}
}
return write;
【在 A*******e 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 已经是O(n)/O(1)了,怎么提交的答案在C/C++里特别慢?用了46ms,但分布图显示不到
: 20ms就够了,甚至还有不到10ms的。试着用equal_range跳着来,结果更慢,56ms。这
: 里面有啥秘诀?
: class Solution {
: public:
: int removeDuplicates(int A[], int n) {
: if (n == 0) {
: return 0;
: }
: int dup_count = 0;
r*n
15 楼
求包养,求交往。。。
r*7
18 楼
哈哈,貌似ls都答的让你很无语哈
我不知道leetcode的机器每次run case是否都是一个fixed resource的container,如
果不是的话可能和当前机器的负载也有关吧。
不知道他们是不是多核然后compiler是否自动优化成多线程。不然把for循环break成多
路然后合并,可能操作的次数要稍微多一点儿,但是并行的block size如果比较合适应
该运行速度会变快。而且最后合并的时候没有比较操作只有mov的指令,因为消耗的CPU
时钟少所以thread的priority会比较高,这样TLB,L1的命中率也会很高。我觉得你可
以尝试get一下cpu number然后break一下试试。。。
【在 A*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 代码已经贴了。常数因子是多少,有没有用复杂语言结构不是一目了然吗?
: 我只想确认算法上是否最优。
我不知道leetcode的机器每次run case是否都是一个fixed resource的container,如
果不是的话可能和当前机器的负载也有关吧。
不知道他们是不是多核然后compiler是否自动优化成多线程。不然把for循环break成多
路然后合并,可能操作的次数要稍微多一点儿,但是并行的block size如果比较合适应
该运行速度会变快。而且最后合并的时候没有比较操作只有mov的指令,因为消耗的CPU
时钟少所以thread的priority会比较高,这样TLB,L1的命中率也会很高。我觉得你可
以尝试get一下cpu number然后break一下试试。。。
【在 A*******e 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 代码已经贴了。常数因子是多少,有没有用复杂语言结构不是一目了然吗?
: 我只想确认算法上是否最优。
A*e
22 楼
至少看到一个简洁写法,有收获。:)
CPU
【在 r****7 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 哈哈,貌似ls都答的让你很无语哈
: 我不知道leetcode的机器每次run case是否都是一个fixed resource的container,如
: 果不是的话可能和当前机器的负载也有关吧。
: 不知道他们是不是多核然后compiler是否自动优化成多线程。不然把for循环break成多
: 路然后合并,可能操作的次数要稍微多一点儿,但是并行的block size如果比较合适应
: 该运行速度会变快。而且最后合并的时候没有比较操作只有mov的指令,因为消耗的CPU
: 时钟少所以thread的priority会比较高,这样TLB,L1的命中率也会很高。我觉得你可
: 以尝试get一下cpu number然后break一下试试。。。
CPU
【在 r****7 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 哈哈,貌似ls都答的让你很无语哈
: 我不知道leetcode的机器每次run case是否都是一个fixed resource的container,如
: 果不是的话可能和当前机器的负载也有关吧。
: 不知道他们是不是多核然后compiler是否自动优化成多线程。不然把for循环break成多
: 路然后合并,可能操作的次数要稍微多一点儿,但是并行的block size如果比较合适应
: 该运行速度会变快。而且最后合并的时候没有比较操作只有mov的指令,因为消耗的CPU
: 时钟少所以thread的priority会比较高,这样TLB,L1的命中率也会很高。我觉得你可
: 以尝试get一下cpu number然后break一下试试。。。
x*1
24 楼
回字的4种写法都学会了?
相关阅读
GX8和Pen-F对比评测,哪个是更好的相机刚收到BH的5D3,镜头没有独立包装怎么卖??MC-11官方支持镜头列表女模特摔跤馆 引大批男性花钱买揍 (转载)单反相机美国还是中国购买? (转载)请大家给推荐一个室内照相的KNIT求推荐一款三脚架!谢谢!adorama的微单机身E-能买么?Sigma big deals用 SONY RX1 拍了几张佳能ref 15%!最近买的可pricematch认真表演的F22和打酱油的F35-Langley基地开放日costco sony a6000 onsale神级的防抖, 对焦不行也是枉然studio flashlight kit有购买推荐文章吗?Canon EF 16-35mm f/2.8L III Coming in June [CR3]想trade in 6d红圈狗头套装 换黑卡对焦很快的卡片机mc11评测来了拍照8年再乱弹