一道布隆berger的电面题

给一个范围[n,m], 找到这个范围内所有的完全平方数，要求平方数的每个数字不重复

楼主只能想到先找平方数，然后循环用set检查重复的算法，貌似还有更好的解法？

题我都看不懂， 希望你解释的再好一点。

我理解是
1）给定从n 到 m 的范围， n and m inclusive
2) [完全] 平方数定义是 x * x, 所以目标是寻找 distinct x 使得 n <= x * x <= m

如果只是这两个要求的话， 你有几种做法
1） 从 a = (int) sqrt(n) 开始朝上数， 一直数到 a * a > m 为止。 这中间的数字都满足要求， On的做法
2）直接做 n的方根， m的方根， 中间的差即个数。 O1的做法。

好的，比如说给定一个范围1-100，其中的平方数是1 4 9 16 25 36 49 64 81 100，其中100里面有两个0，需要去掉，返回其他的。

首先由于阿拉伯数字只有十个，可以注意到这样的完全平方数不会超过10^10
所以直接从sqrt(N)枚举到sqrt(M)，然后检查其平方各位数字是否互不相同就行，复杂度是O(sqrt(N))的，lz做法完全OK

tinylic 发表于 2018-8-4 00:03
首先由于阿拉伯数字只有十个，可以注意到这样的完全平方数不会超过10^10
所以直接从sqrt(N)枚举到 ...

或者由于这样的数不超过10^5个，把它们全预处理出来，每次二分查找也行

那确实没什么好做法, 挨个看吧.. 毕竟平方没什么好的计算方法.

所以你 sqrt(n) 到 sqrt(m) 我们算 sqr n 时间好了.
然后你对着每个 i * i 看0-9是否存在过了. 可以用一个 int nums[9] 或者 bit manipulation.
这个是数字长度时间. 如果你的n都是int的话那就不会超过10次操作, 可以算o1时间.

补充内容 (2018-8-4 00:42):
遍历是O[n]

然后呢， 弄明白了吗？发个贴就算完事了？