LeetCode 简略题解 - 401~500 - 知乎专栏
解法2：这个解法很巧妙，我鼓捣了一个多钟头才想明白。首先，这题除了O(N ^ 2)的暴力解法，肯定有更高效的解法。为什么？因为这是个关于"排序"的问题，你们都知道O(N * logN)是比较排序的下界。而且这题涉及到了数数。所以，我决定用树状数组试试，结果还真搞出来了。虽然实际复杂度不是O(N * logN)，而是O(N * log ^2 N)。但总体的思想，还是二分搜索。用树状数组，只是为了区间求和。
Read full article from LeetCode 简略题解 - 401~500 - 知乎专栏
No comments:
Post a Comment