Skip to content

Instantly share code, notes, and snippets.

@gcrfelix
Created October 17, 2015 18:29
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save gcrfelix/4d54afde1a7f88ca32ba to your computer and use it in GitHub Desktop.
Save gcrfelix/4d54afde1a7f88ca32ba to your computer and use it in GitHub Desktop.
一个数如果能用两个立方数相加并且至少有两组这样的立方数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