我正在尝试用 JavaScript 解决 HackerRank“查找因子”问题,但我一直达到 10 秒的时间限制。
这个问题给了我们正整数 n 和 k,并要求我们找到 n 的 k最小除数,如果 n 的除数少于 k,则为 -1。
例如,如果 n 是 15,k 是 3,那么我们需要返回 5,因为 15 的约数是 [1, 3, 5, 15]。
我尝试了自己的想法,以及网上找到的解决方案,但都失败了。
示例:
function pthFactor(n, k) {
let arr = [];
for (let i = 1; i <= n; i++) {
if (n % i === 0) {
arr.push(i);
}
if (arr.length === k) {
return arr[arr.length - 1];
}
}
if (arr.length !== k) {
return -1;
}
};
或
var kthFactor = function (n, k) {
let factors = [1]
for (let i = 2; i <= Math.floor(n/2); i++) {
if (n % i == 0) factors.push(i)
}
factors.push(n)
return factors.length < k ? -1 : factors[k-1]
};
我还尝试使用
Math.sqrt
以避免循环n
次;没有任何改善。
我做错了什么?
我是否需要了解更多 for 循环才能解决这个问题? (也许是动态规划?)
我在 HackerRank 上找不到这个挑战,但找到了 1492。 LeetCode 上 n 挑战的第 k 个因子似乎与您描述的相同:
给定两个正整数
和n
。k
整数
的因子被定义为整数n
,其中i
。n % i == 0
考虑按
升序排序的n
的所有因子的列表,返回此列表中的因子,或者如果kth
n
少于因子,则返回k
-1。
奇怪的是,您在第一个代码块中使用了名称
pthFactor
,而相关参数的名称是 k
而不是 p
。这真是令人困惑。
我还尝试了
等,以免循环Math.sqrt
次n
您不能只考虑 𝑛 平方根以下的因子。例如,6 是 12 的因数,甚至 12 也是 12 的因数。
但是,大约 一半 的所有因子都在平方根范围内。那些较大的因数等于用那些较小的因数进行除法得到的商。所以最后,你可以停在平方根处,前提是你收集了所有这些商,如果你还没有达到𝑘第因子,则从这些商中选择正确的一个。
所以这个想法可以这样实现:
var kthFactor = function(n, k) {
let bigFactors = [];
let quotient = n + 1;
for (let factor = 1; factor < quotient; factor++) {
if (n % factor === 0) {
quotient = n / factor;
k--;
if (k <= 0) return factor;
if (factor >= quotient) break;
bigFactors.push(quotient);
}
}
return bigFactors[bigFactors.length - k] ?? -1;
};
// A few test cases:
console.log(kthFactor(12, 3)); // 3
console.log(kthFactor(7, 2)); // 7
console.log(kthFactor(16, 5)); // 16
console.log(kthFactor(27, 5)); // -1
console.log(kthFactor(927, 1)); // 1
这段代码使用与trincot的答案相同的算法,但我认为用递归来表达更简单:
const kthFactor = (n, k, f = 1, r = []) =>
f * f > n
? r [k - 1] ?? -1
: n % f == 0
? k == 1 ? f : kthFactor (n, k - 1, f + 1, f * f == n ? r : [n / f, ...r])
: kthFactor (n, k, f + 1, r)
console .log (kthFactor (12, 3)); //=> 3
console .log (kthFactor (7, 2)); //=> 7
console .log (kthFactor (16, 5)); //=> 16
console .log (kthFactor (27, 5)); //=> -1
console .log (kthFactor (927, 1)); //=> 1
在这里,我们跟踪正在测试的因子 (
f
) 和要测试的剩余数字 (r
),每当我们发现新因子时就减少 k
,并将商 n / f
添加到剩余数字中,每一步都增加f
,当我们变得太大时停止(f * f > n
),然后在剩余数字的有序列表中找到索引,当k
为1
时返回因子,然后简单地重复否则增加一个因子。
唯一棘手的一点是完美平方的处理,其中平方根只能计算一次,因此如果
f * f == n
,我们不会将其添加到剩余的数字中。
由于递归,这仅适用于这么大的
k
。 虽然我们可以以简单的方式使尾部递归,但在撰写本文时这并不重要,因为尾部调用优化在大多数引擎中仍然没有发生。