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 的大作中提到】
: 已经是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 的大作中提到】
: 已经是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;
x*k
5 楼
AUV，原来这帖是她发的
【在 S*M 的大作中提到】
: 【 以下文字转载自 Fashion 讨论区 】
: 发信人: lemma (证明定理), 信区: Fashion
: 标 题: 求意见，这个撞色是不是有点过了？
: 发信站: BBS 未名空间站 (Mon Jun 20 18:01:30 2011, 美东)
: 去H&M逛了一圈，好想都买下来，我要忍住，忍住。。。。
: 求意见，这个撞色是不是有点过了？
【在 S*M 的大作中提到】
: 【 以下文字转载自 Fashion 讨论区 】
: 发信人: lemma (证明定理), 信区: Fashion
: 标 题: 求意见，这个撞色是不是有点过了？
: 发信站: BBS 未名空间站 (Mon Jun 20 18:01:30 2011, 美东)
: 去H&M逛了一圈，好想都买下来，我要忍住，忍住。。。。
: 求意见，这个撞色是不是有点过了？
c*e
6 楼
算法的时间复杂度，及其优化
和实际计算机上执行耗费的时间，以及优化
是两个不同层面的性能问题
你这样混到一起谈，就说不清了
同样的o(n)同样的算法同样的逻辑，我在语言和指令级别给你优化，差个100倍也不奇怪
和实际计算机上执行耗费的时间，以及优化
是两个不同层面的性能问题
你这样混到一起谈，就说不清了
同样的o(n)同样的算法同样的逻辑，我在语言和指令级别给你优化，差个100倍也不奇怪
b*5
7 楼
Oh...攒眼熟ID 奔。。。
A*e
8 楼
leetcode用的应该是同样的机器啊。
奇怪
【在 c*******e 的大作中提到】
: 算法的时间复杂度，及其优化
: 和实际计算机上执行耗费的时间，以及优化
: 是两个不同层面的性能问题
: 你这样混到一起谈，就说不清了
: 同样的o(n)同样的算法同样的逻辑，我在语言和指令级别给你优化，差个100倍也不奇怪
奇怪
【在 c*******e 的大作中提到】
: 算法的时间复杂度，及其优化
: 和实际计算机上执行耗费的时间，以及优化
: 是两个不同层面的性能问题
: 你这样混到一起谈，就说不清了
: 同样的o(n)同样的算法同样的逻辑，我在语言和指令级别给你优化，差个100倍也不奇怪
a*l
9 楼
清秀的脸庞，正。
c*e
10 楼
看来你的基本概念不清楚
1.
O(2 * n)
O(10 * n)
O(100 * n)
都会被视同 O(n)的
2.时间复杂度，以虚拟的“单位操作”次数为衡量，不以CPU时间为衡量
if (x == 3)
和 if (Integer.compare(x, 3) == 0)
都做n次，那么都是O(n)
但是后者实际执行时消耗的CPU时间肯定多很多
这就是我前面说的语言级别的优化。我前面说的，和更快的CPU无关。
【在 A*******e 的大作中提到】
: leetcode用的应该是同样的机器啊。
:
: 奇怪
1.
O(2 * n)
O(10 * n)
O(100 * n)
都会被视同 O(n)的
2.时间复杂度，以虚拟的“单位操作”次数为衡量，不以CPU时间为衡量
if (x == 3)
和 if (Integer.compare(x, 3) == 0)
都做n次，那么都是O(n)
但是后者实际执行时消耗的CPU时间肯定多很多
这就是我前面说的语言级别的优化。我前面说的，和更快的CPU无关。
【在 A*******e 的大作中提到】
: leetcode用的应该是同样的机器啊。
:
: 奇怪
l*a
11 楼
就知道lemma是美女
【在 S*M 的大作中提到】
: 【 以下文字转载自 Fashion 讨论区 】
: 发信人: lemma (证明定理), 信区: Fashion
: 标 题: 求意见，这个撞色是不是有点过了？
: 发信站: BBS 未名空间站 (Mon Jun 20 18:01:30 2011, 美东)
: 去H&M逛了一圈，好想都买下来，我要忍住，忍住。。。。
: 求意见，这个撞色是不是有点过了？
【在 S*M 的大作中提到】
: 【 以下文字转载自 Fashion 讨论区 】
: 发信人: lemma (证明定理), 信区: Fashion
: 标 题: 求意见，这个撞色是不是有点过了？
: 发信站: BBS 未名空间站 (Mon Jun 20 18:01:30 2011, 美东)
: 去H&M逛了一圈，好想都买下来，我要忍住，忍住。。。。
: 求意见，这个撞色是不是有点过了？
A*e
12 楼
代码已经贴了。常数因子是多少，有没有用复杂语言结构不是一目了然吗？
我只想确认算法上是否最优。
【在 c*******e 的大作中提到】
: 看来你的基本概念不清楚
: 1.
: O(2 * n)
: O(10 * n)
: O(100 * n)
: 都会被视同 O(n)的
: 2.时间复杂度，以虚拟的“单位操作”次数为衡量，不以CPU时间为衡量
: if (x == 3)
: 和 if (Integer.compare(x, 3) == 0)
: 都做n次，那么都是O(n)
我只想确认算法上是否最优。
【在 c*******e 的大作中提到】
: 看来你的基本概念不清楚
: 1.
: O(2 * n)
: O(10 * n)
: O(100 * n)
: 都会被视同 O(n)的
: 2.时间复杂度，以虚拟的“单位操作”次数为衡量，不以CPU时间为衡量
: if (x == 3)
: 和 if (Integer.compare(x, 3) == 0)
: 都做n次，那么都是O(n)
f*p
13 楼
差点看成热妈的马甲了
【在 l***a 的大作中提到】
: 就知道lemma是美女
【在 l***a 的大作中提到】
: 就知道lemma是美女
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 的大作中提到】
: 已经是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 的大作中提到】
: 已经是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 楼
求包养，求交往。。。
c*n
16 楼
“算法最优” 就是code structure 符合o（n）就行， 没人care 那个常数。
leet code 没法测你的 runtime 随input size 的变化， 那需要太多测试点， 它只好
给个大致的time limit 防止死循环 和特别不靠谱的算法
【在 A*******e 的大作中提到】
: 代码已经贴了。常数因子是多少，有没有用复杂语言结构不是一目了然吗？
: 我只想确认算法上是否最优。
leet code 没法测你的 runtime 随input size 的变化， 那需要太多测试点， 它只好
给个大致的time limit 防止死循环 和特别不靠谱的算法
【在 A*******e 的大作中提到】
: 代码已经贴了。常数因子是多少，有没有用复杂语言结构不是一目了然吗？
: 我只想确认算法上是否最优。
f*p
17 楼
转发你LD阅
【在 r*********n 的大作中提到】
: 求包养，求交往。。。
【在 r*********n 的大作中提到】
: 求包养，求交往。。。
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 的大作中提到】
: 代码已经贴了。常数因子是多少，有没有用复杂语言结构不是一目了然吗？
: 我只想确认算法上是否最优。
我不知道leetcode的机器每次run case是否都是一个fixed resource的container，如
果不是的话可能和当前机器的负载也有关吧。
不知道他们是不是多核然后compiler是否自动优化成多线程。不然把for循环break成多
路然后合并，可能操作的次数要稍微多一点儿，但是并行的block size如果比较合适应
该运行速度会变快。而且最后合并的时候没有比较操作只有mov的指令，因为消耗的CPU
时钟少所以thread的priority会比较高，这样TLB，L1的命中率也会很高。我觉得你可
以尝试get一下cpu number然后break一下试试。。。
【在 A*******e 的大作中提到】
: 代码已经贴了。常数因子是多少，有没有用复杂语言结构不是一目了然吗？
: 我只想确认算法上是否最优。
l*a
19 楼
你让热妈奔ld
【在 f********p 的大作中提到】
: 差点看成热妈的马甲了
【在 f********p 的大作中提到】
: 差点看成热妈的马甲了
A*e
20 楼
这么写确实简洁，有点像CLRS上快排partition的写法。不过可读性真的好吗？
【在 l*****a 的大作中提到】
: 你写得有点难懂啊,这么写是不是清楚点?
: int write=1;
: for(int read=1;read<=A.length-1;read++) {
: if(A[read]!=A[write-1]) {
: A[write++]=A[read];
: }
: }
: return write;
【在 l*****a 的大作中提到】
: 你写得有点难懂啊,这么写是不是清楚点?
: int write=1;
: for(int read=1;read<=A.length-1;read++) {
: if(A[read]!=A[write-1]) {
: A[write++]=A[read];
: }
: }
: return write;
f*p
21 楼
热妈能把自己奔了就性了
【在 l***a 的大作中提到】
: 你让热妈奔ld
【在 l***a 的大作中提到】
: 你让热妈奔ld
A*e
22 楼
至少看到一个简洁写法，有收获。:)
CPU
【在 r****7 的大作中提到】
: 哈哈，貌似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 的大作中提到】
: 哈哈，貌似ls都答的让你很无语哈
: 我不知道leetcode的机器每次run case是否都是一个fixed resource的container，如
: 果不是的话可能和当前机器的负载也有关吧。
: 不知道他们是不是多核然后compiler是否自动优化成多线程。不然把for循环break成多
: 路然后合并，可能操作的次数要稍微多一点儿，但是并行的block size如果比较合适应
: 该运行速度会变快。而且最后合并的时候没有比较操作只有mov的指令，因为消耗的CPU
: 时钟少所以thread的priority会比较高，这样TLB，L1的命中率也会很高。我觉得你可
: 以尝试get一下cpu number然后break一下试试。。。
x*k
23 楼
人娃都有了
【在 r*********n 的大作中提到】
: 求包养，求交往。。。
【在 r*********n 的大作中提到】
: 求包养，求交往。。。
x*1
24 楼
回字的4种写法都学会了？
n*b
25 楼
求playdate
【在 x***k 的大作中提到】
: 人娃都有了
【在 x***k 的大作中提到】
: 人娃都有了
r*7
26 楼
我try了一下貌似也差不多40ms
【在 A*******e 的大作中提到】
: 至少看到一个简洁写法，有收获。:)
:
: CPU
【在 A*******e 的大作中提到】
: 至少看到一个简洁写法，有收获。:)
:
: CPU
x*k
27 楼
我会替你转告的
【在 n**b 的大作中提到】
: 求playdate
【在 n**b 的大作中提到】
: 求playdate
r*n
28 楼
刚被LD发现，中午饭只能喝西北风了。。。。
【在 f********p 的大作中提到】
: 转发你LD阅
【在 f********p 的大作中提到】
: 转发你LD阅
m*7
29 楼
【在 n**b 的大作中提到】
: 求playdate
x*3
30 楼
co-kan
【在 f********p 的大作中提到】
: 差点看成热妈的马甲了
S*M
31 楼
多去隔壁上片
【在 r*********n 的大作中提到】
: 求包养，求交往。。。
【在 r*********n 的大作中提到】
: 求包养，求交往。。。
相关阅读
福特野马真不是吹的纠结。。Staub的Dutch Oven值得买么百听不厌，老歌一首 (转载)[FS] Canon EOS M with 18-55mm and 22mm lens35mm 1.8g DX for 140 good deal没有谈谈D810，铁丝们都去哪了鞋厂发布something small[fs]sony a6000 body only $550最终还是买了70-200mm F4 IS大家预测一下6D什么时候出mark II吧fuji xm1 deal??现在16-35F4最好的价格是1100不到ebay 买个 135 f2 是坏的。。。。求推荐camcorder16-35mm f/2.8L II 还是 F4 IS国内山寨完善能力真强——百诺雨燕200摄影双肩包这个镜头谁用过？Opteka 650-2600mm HD Telephoto Zoom Lens微单推荐[fs] a7S Full Frame Mirrorless Camera70D deal @buydig