我的代码如下:

以下是Leetcode上提交内容的运行时分布:

问题是，即使在C中有很多提交的代码带有O(log(m + n))，但我认为我的代码的时间复杂度是O(m + n).因此根据分布图，我的代码在Leetcode上排名前2％是没有道理的.当然，对于少量输入而言，线性比对数更快，但是测试用例足够大，可以被O(log(m + n))击败.我不知道为什么我的代码以这种速度通过.

将非常感谢您的评论！

在我的最高注释中:在函数开始时分配 new .如果执行任何提早转义" return 语句，则会泄漏内存.

那么我是否必须在每个 return 语句中放入 free()?或者我该如何修正我的代码?

直到 早期逃逸的最高代码段之后，才执行 malloc .

然后，在底部执行 free .为此，您需要一个额外的变量来保存返回值，以便可以安全地执行 free(new)(例如 double retval; )

旁注:用 new [i] 替换(例如) *(new + i)通常比较干净.另外，将代码保持为< = 80个字符/行也是一种很好的样式.

这是修复代码的一种方法[请原谅免费的样式清理]:

但是，就我个人而言，我不喜欢函数中的多个 return 语句.[使用 gdb ]调试起来比较困难，因为您必须在每个 return 上设置一个断点.

这里是使用 do {...} while(0); 作为一次通过"循环的版本，它使我们可以消除 if/else 阶梯"逻辑(我个人也不喜欢)，底部只有一个单 return .YMMV ...

更新:

谢谢！我明白了您的代码比我的代码更真实！但是您如何看待他们之间的表现呢?( if/else 和 do {...} while(0)).因为如果我们假设编译器可以像我们通常期望的那样工作，那么 if/else 比经过修改的代码中 do {...} 中的if/else 要快.再次非常感谢！

实际上，如果我们反汇编两个版本(用-O2编译)，则do/while版本会比汇编指令短4个.

但是，要对其进行调整，必须对其进行测量.

优化器几乎会使它们相似.

该函数的大部分时间都花在 for 循环中，这两者都是相同的.循环的速度使 do/while 的任何额外开销相形见which，这可能是一两个汇编程序的指令[但是， do/while 的指令却更少].

因此，调整/优化函数的序言/结尾代码通常不值得.加快循环速度.

要进行调整/优化，请进行性能分析以确定代码在哪里花费了最多时间(或者对于这个简单的事情，显然是循环)，或者在函数上添加了时间戳记并获得了经过的时间[或各个子部分]

正如我提到的，很难为具有多个 return 语句的函数添加一个断点.

此外，有时您无法附加调试器.或者，很难找到一个有意义的地方放置断点.例如，如果您的某个程序可以正常运行(例如)几天，然后在(例如)63小时后中止，则可能需要进行内部基准测试和 printf 样式调试:

插入带有第二个版本的调试打印语句要容易得多.

顺便说一句，我一直在做这种事情.而且，我的特长之一是快速编码和提高性能(因为我做了很多实时编码).

My code is below :

And below is the submissions's runtime distribution on Leetcode :

The Question is, even if there are a lot of submitted codes with O(log (m+n)) in C but I think my code's Time complexity is O(m+n). so it doesn't make sense that my code is top 2% on Leetcode according to the distribution graph. of course linear is faster than log to a small amount of inputs but the test-cases are enough big to get beaten by O(log (m+n)). I don't know why my code get passed with that rate.

will greatly appreciate your comments!

From my top comment: You allocate new at the start of the function. If any of the "early escape" return statements are executed, you'll leak memory.

So do I have to put free() in every return statement? or how can i fix my code?

Don't do the malloc until after the top block of early escapes.

And, do the free at the bottom. To do this, you'll need an extra variable to hold the return value so you can safely do the free(new) (e.g. double retval;)

Side note: It's usually cleaner to replace (e.g.) *(new + i) with new[i]. Also, holding the code to <= 80 chars / line is also a good style.

Here's one way to fix your code [please pardon the gratuitous style cleanup]:

But, personally, I dislike multiple return statements in a function. It's harder to debug [using gdb] because you'd have to set a breakpoint on each return.

Here's a version that uses a do { ... } while (0); as a "once through" loop that allows us to eliminate the if/else "ladder" logic [which I also personally dislike] and have only a single return at the bottom. YMMV ...

UPDATE:

thanks! I understood. your code is more clear than mine for real!. but what do you think about the performance between them? ( if/else and do{...}while(0)). because if we assume the compiler would work as we generally expect, if/else is faster than if if which is in do{...} in the revised code. thanks a lot again!

Actually, if we disassemble both versions [compiled with -O2], the do/while version is 4 assembly instructions shorter.

But, in order to tune it, you have to measure it.

The optimizer will pretty much make them similar.

The main bulk of the time of the function is spent in the for loop, which is the same for both. The speed of the loop dwarfs any extra overhead of do/while which might be an assembler instruction or two [but, again the do/while has fewer instructions].

So, tuning/optimizing the prolog/epilog code of the function isn't [usually] worth it. Speeding up the loop is.

To tune/optimize, either do profiling to determine where the code spends the most amount of time [or for something this simple, it's obviously the loop], or add timestamping and get elapsed time on the function [or various subparts].

As I mentioned, it's hard to add a breakpoint for a function that has multiple return statements.

Also, sometimes you can't attach a debugger. Or, it's difficult to find a meaningful place to put a breakpoint. For example, if you have a program that runs fine for (e.g.) days, and then aborts after (e.g.) 63 hours, you may need to do internal benchmarking and printf style debugging:

It's much easier to insert the debug print statements with the second version.

BTW, I do this sort of thing all the time. And, one of my fortes is fast code and performance improvement [as I do a lot of realtime coding].