Hackerrank“查找因子”（在 javascript 中）由于时间限制而失败？

Question

我必须找到所有能整除一个数字的正数因子，然后返回列表中的

p^th

元素，按升序排序。 如果没有的话

p^th return 0.

我测试了几乎所有我能解决并在网上找到的答案：

示例：

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]
};

但是它没有达到 10 秒的时间限制。

我做错了什么？

顺便说一句，我也尝试了

Math.sqrt

等，以免循环

n

次。效果不太好。 除了 for 循环之外，我还需要了解更多吗？像动态规划等来解决这个问题？

Answer 1

我在 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

Answer 2

这段代码使用与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

。 虽然我们可以以简单的方式使尾部递归，但在撰写本文时这并不重要，因为尾部调用优化在大多数引擎中仍然没有发生。