algorithm - 棘手的面试难题

Question

您在 Javascript 中有此代码（即使语言选择无关紧要）：

var arr = new Array(101);
for (skip = 1; skip <= 100; skip++) {
    for (i = 0; i <= 100; i+= skip) {
        arr[i] = !arr[i];
    }
}

显然，这段代码运行后，数组中会有一堆真假值。如果 arr[i] 被触摸了偶数次，则为假，否则为真。

问题是这些价值形成了什么样的模式？你能快速判断 arr[15] 是真还是假？arr[81] 呢？

我知道答案（当 x 是某个整数的平方时，arr[x] 为真），但我不明白我应该如何在面试中快速得出答案？

额外的问题是这段代码的时间复杂度是多少，假设您对 N 个数组元素执行此操作（我将在下面回答）？

score 17 · Accepted Answer

所有完美的方形项目都是真的，所有其他的都是假的。

这可以通过以下事实来解释：完美正方形具有奇数个唯一因子，而所有其他正方形具有偶数个。这是因为完美平方的平方根仅计为一个因素。

一个数字会针对它所具有的每个因素切换一次，例如：

12 -> 1, 2, 3, 4, 6, 12 -> an even number, so still false
16 -> 1, 2, 4, 8, 16 -> an odd number, so true

奖励：该算法执行 n + n/2 + n/3 ...切换导致 O(n log n) 时间（在另一个答案中解释得更好）。

score 9 · Accepted Answer

如果对 N 个元素执行此操作，则将有 N + N/2 + N/3 + ... 操作。是调和级数，级数的部分和呈对数增长。因此，时间复杂度为 O(n*log n)

score 5 · Accepted Answer

所有带有整数平方的数字都为真，其他数字为假。

证明：

我们将看到，只有将它们除以奇数的数字才会为真：

表示数字 N > 0。

根据代数中的一句话，有 k 个不同的素数 p1,p2,...pk 和非零整数 m1 m2,...,mk

例如：N = p1^m1 * p2^m2 ... pk^mk。

因此，除 N 的数 =

(m1 + 1) (m2 + 1) ...*(mk + 1)。那是来自组合学。

这个数字是奇数 <=> 对于每个 1 <= j <= k , mj + 1 是奇数 <=> 对于每个 1<= j <= k, mj 是偶数 <=> 存在 n1,n2,..., nk 个非零元素，例如 mj = 2nj，每个 1 <= j <= k。

所以我们得到：

N = p1^2n1 * p2^2n2 .. pk^2nk => N = (p1^n1 * p2^n2 ... pk^nk)^2，如我们所愿。

这是一个数学证明。

3 回答 3