Created
October 17, 2015 18:29
-
-
Save gcrfelix/4d54afde1a7f88ca32ba to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
一个数如果能用两个立方数相加并且至少有两组这样的立方数pair,那么就是good number。print 小于等于n的所有good number。 | |
分析时间复杂度 | |
1. 创建数组,存储所有 ≤n 的立方数,value = index^3, 一共m个(m = n^1/3)--> O(m) | |
2. 在这m个立方数中,找两组和相等的 | |
2.1 一共会有m^2个可能的和(包括重复) | |
2.2 sort --> O(m^2logm^2) = O(m^2logm). | |
2.3 scan 一遍,找consecutive的、相等的、长度≥2的子数组个数 --> O(m^2) | |
(2.2和2.3也可以用hashmap做) | |
最后的总复杂度为O(m^2logm) ;带入m = n^(1/3) 得O(n^(2/3)logn) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment