注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
给定公式为2^i * 3^j * 5^k * 7^l, 其中i,j,k,l为非负整数。根据不同的i/j/k/l这个公式可以生成不同的数,把这些数从小到大排列,要求找出其中第n个数字。要求用O(n)的时间。这个是Leetcode上的题吗?
本质就是找出所有质因子只有2/3/5/7的数字里面的第n个,感觉应该用类似筛法把11及以上所有质数的倍数去掉,然后剩下的数第n个数就是结果。有几个问题:
1. 筛法的数组应该开多大?这个跟Leetcode 204不一样,并不是划倍数划到n就可以了,因为这里的第n个数肯定要大于n。数组开到多大保险?感觉2n应该就够了吧?不过这个能证明吗?还是随着n的增大数组越来越大?那就得动态扩容?不过这样是不是就没法保证O(n)了?
2. 另外筛法本身也不是O(n)的,而是O(n log log n)。当然可以argue如果n是int型的,log log n最大也就3.07。不知道有没有确实是O(n)的方法?因为毕竟不是要求找出前n个数,而是仅仅要第n个数,是否有办法能更快?
如果不用筛法,直接遍历i/j/k/l的各种组合是不是更慢?有没有一种遍历法可以保证生成的数字递增?
|