我如何在更短的时间内完成这个问题？

Question

编辑：所以我将代码更改为以下内容：

function countTinyPairs(a, b, k) {
    let pairs = 0;
    let arr = [];
    b.reverse()
    for (num in a) {
        result = String(a[num]) + String(b[num])
        if (result < k) {
            pairs++
        }
    }
    return pairs
}

它的工作原理完全一样，不需要检查新的 arr/push 等。这个运行会不会用得更短？有没有办法自己检查需要多长时间？

我正在做一个 Codesignal javascript 练习测试（现已完成）。我度过了一段非常艰难的时期，现在我知道我需要更多的练习才能考虑进行实际测试。其中一个问题是：

"给定两个长度相同的整数数组 a 和 b，以及一个整数 k。我们将从左到右遍历数组 a，同时从右到左遍历数组 b，并查找在对 (x, y) 处，其中 x 来自 a，y 来自 b。如果连接 xy 严格小于 k，则这样的一对称为 tiny。"

这是我写的代码：

function countTinyPairs(a, b, k) {
    let pairs = 0;
    let arr = [];
    b.reverse()
    for (num in a) {
        for (num in b) {
            result = String(a[num]) + String(b[num])
            if (result < k) {
                if ((arr.findIndex(e => e === result)) === -1) {
                    arr.push(String(result));
                    pairs++
                }        
            }
        }
    }
    return pairs
}

有效，但执行时间限制为 4 秒。有一个隐藏的测试用例，我的函数需要超过 4 秒才能完成（我假设数组有大量数字）。我还没有学到任何关于 Big O（或它的名字）的知识，所以我对它一无所知。

我想我必须先了解它才能成功地自己解决这个问题？或者，我只是写了糟糕的代码，并且可以在不了解 Big O 的情况下用更好的代码来完成它吗？

Answer 1

You are given two arrays of integers a and b of the same length。长度相同，因此我们只需要迭代一次，将其从 O(n^2) 改进为 O(n)。您仍然需要检查每个元素，因此这是该问题的最佳可能复杂度。

检查重复项的 if 语句与变量 pairs 一样不需要。您可以使用 Set 来检查重复项，最后 return 它的 length 而不是手动计算对数。

我附上下面的示例解决方案：

const countTinyPairs = (a, b, k) => {
        const set = new Set();
        for (let i = 0, j = b.length-1; i < a.length; i++, j--) {
                const result = String(a[i]) + String(b[j])
                if (result < k) {
                    set.add(result);
                }
        }
        return set.size;
    }

    console.log(countTinyPairs([1,2,3,4,5], [1,2,3,4,5], 40))

Edit 没有必要有一个名为 j 的单独变量，但我认为将它存储在一个变量中更具可读性。

如果我们不需要查重的话，这样写就可以了：

   const countTinyPairs = (a, b, k) => {
        let pairs;
        for (let i = 0, j = b.length-1; i < a.length; i++, j--) {
                if (String(a[i]) + String(b[j])< k) pairs++
        }
        return pairs;
    }

Answer 2

你的代码的复杂度是 O(n^2)

这是我的解决方法。我希望我做对了任务，请post一些input/output的例子。

如果 a 和 b 的长度相等，您可以用一个循环遍历它们。复杂度为 O(n)，其中 n 是 a.
的长度

为什么要检查重复项？这是要求吗？

function test(a,b,k)
{
  let x,y,i,xy, result =[];
  for (i=0;i<a.length;i++)
  {
     x = a[i];
     y = b[b.length - 1 -i]
     xy = parseInt([x,y].join(''));
     if (xy < k) result.push(xy);
  }
  return result;
 }
 let a = [1,2,3,4,5], b=[4,5,6,7,8], k = 40;
 console.log(test(a,b,k));

 // Output: [18, 27, 36]

Answer 3

首先，不需要多次循环。你有三个:

b.reverse() 将反转 b in-place，可能 O(n) 复杂。就算是O(log n)也没必要
for (num in a) 在 O(n) 中迭代 a。
for (num in b) 在 O(n) 中迭代 b。但是，由于它是一个内部循环，因此总数为 O(n^2).
arr.findIndex(e => e === result) 将在找到的任何对上触发另一个 O(m) 迭代。根据 k 的值，可能只有几次或很多次。在O(n^2)中已经已经，所以最坏的情况是k的高值覆盖了每对组合，因此每次都会触发，因此你会得到 O(n^3) 复杂度。

消除 `a` 和 `b`

上的多个循环

鉴于 a 和 b 的长度相等，我们可以用一个循环简单地遍历两个数组。为了实现反向迭代，我们可以使用基本算法来获得 b 的索引，该索引与末尾的距离与 a 的索引与开头的距离相同。或者换句话说，您可以这样做以在两个方向上同时迭代两个数组：

const a = [2, 9, 2];
const b = [5, 3, 5];

for (let i = 0; i < a.length; i++) {
  const j = b.length - i - 1; //reverse the index for `b`
  
  console.log(`${a[i]}, ${b[j]}`);
}

请注意 a.length 和 b.length 可以互换，因为问题描述说它们是相同的。

删除 `arr`

中的常量查找

下一个问题是 arr 仅在上重复迭代以检查是否存在一对。相反，您可以使用 Set。根据规范，查找和插入将具有 sub-linear 复杂性。许多实现甚至可以给你O(1)。您可以将代码简化为

const pairs = new Set();

/* ... if a pair is found ... */
pairs.add(result);

/* ... produce count ... */
return pairs.size;

总结

完整的解决方案如下所示，您只需同时遍历 a 和 b 一次：

function countTinyPairs(a, b, k) {
  let pairs = new Set();

  for (let i = 0; i < a.length; i++) {
    const j = b.length - i - 1;
    const pair = `${a[i]}${b[j]}`;
    
    if (Number(pair) < k) {
      pairs.add(pair);
    }
  }
  
  return pairs.size;
}

const a = [2, 9, 2];
const b = [5, 3, 5];

console.log(countTinyPairs(a, b, 30));

备选

这也可以使用数组方法来表示，导致更短的代码，代价是使用 .map 和 .filter 的两个循环，然后第三个循环转换为 Set:

function countTinyPairs(a, b, k) {
  let pairs = a
    .map((x, index) => `${x}${b[b.length - index - 1]}`) //produce pair
    .filter(x => Number(x) < k); //leave only tiny ones
    
  return new Set(pairs).size; //deduplicate and count
}

const a = [2, 9, 2];
const b = [5, 3, 5];

console.log(countTinyPairs(a, b, 30));

使用.reduce再次将其缩减为一个循环：

function countTinyPairs(a, b, k) {
  let pairs = a
    .reduce((acc, x, index) => {
      const pair = `${x}${b[b.length - index - 1]}`;
      if (Number(pair) < k) {
        return acc.add(pair);
      }
      return acc;
    }, new Set());
    
  return pairs.size; //deduplicate and count
}

const a = [2, 9, 2];
const b = [5, 3, 5];

console.log(countTinyPairs(a, b, 30));

最后，如果你讨厌自己，你可以把它变成一个单一的表达：

const countTinyPairs = (a, b, k) => 
  a.reduce(
    (acc, x, index) => 
      (pair => (Number(pair) < k) ? acc.add(pair) : acc)
        (`${x}${b[b.length - index - 1]}`), 
    new Set()).size;

const a = [2, 9, 2];
const b = [5, 3, 5];

console.log(countTinyPairs(a, b, 30));

不丢弃重复项

如果不需要去重，那么整个代码就变得更简单——你只需要维护一个计数，甚至不需要收集对：

function countTinyPairs(a, b, k) {
  let pairs = 0;

  for (let i = 0; i < a.length; i++) {
    const j = b.length - i - 1;
    const pair = `${a[i]}${b[j]}`;
    
    if (Number(pair) < k) {
      pairs++;
    }
  }
  
  return pairs;
}

const a = [2, 9, 2];
const b = [5, 3, 5];

console.log(countTinyPairs(a, b, 30));

或使用数组方法：

`.map()` + `.filter()`

function countTinyPairs(a, b, k) {
  let pairs = a
    .map((x, index) => `${x}${b[b.length - index - 1]}`) //produce pair
    .filter(x => Number(x) < k); //leave only tiny ones
    
  return pairs.length;
}

const a = [2, 9, 2];
const b = [5, 3, 5];

console.log(countTinyPairs(a, b, 30));

`.reduce()`

function countTinyPairs(a, b, k) {
  let pairs = a
    .reduce((count, x, index) => {
      const pair = `${x}${b[b.length - index - 1]}`;
      if (Number(pair) < k) {
        return count + 1;
      }
      return count;
    }, 0);
    
  return pairs;
}

const a = [2, 9, 2];
const b = [5, 3, 5];

console.log(countTinyPairs(a, b, 30));

单个表达式`.reduce()`

const countTinyPairs = (a, b, k) => 
  a.reduce(
    (count, x, index) => 
      count + (Number(`${x}${b[b.length - index - 1]}`) < k), 
    0);

const a = [2, 9, 2];
const b = [5, 3, 5];

console.log(countTinyPairs(a, b, 30));

Answer 4

问题的措辞有些模棱两可，没有提供具体的输入和预期的输出也于事无补。这是我根据对问题的理解编写解决方案的方式 -

const countTinyPairs = (a, b, k) =>
  loop
    ( ( [ x, xs ] = likeList(a)
      , [ y, ys ] = likeList([...b].reverse())
      , pairs = 0
      ) =>
      x == null || y == null
        ? pairs
        : recur
            ( xs
            , ys
            , Number(`${x}${y}`) < k
                ? pairs + 1
                : pairs
            )
    )

console.log(countTinyPairs([1,2,3,4,5], [3,4,5,6,7], 40))
// => 3

使用我们自己的通用函数 loop、recur 和 likeList，我们可以显着减少推导出答案所需的概念开销 -

const likeList = (t = [], c = 0) =>
  ({ [Symbol.iterator]: _ => [ t[c], likeList(t, c + 1) ].values() })
  
const recur = (...v) =>
  ({ recur, [Symbol.iterator]: _ => v.values() })
  
const loop = (f, ...init) =>
{ let r = f(...init)
  while (r && r.recur === recur)
    r = f(...r)
  return r
}

如果您想详细了解这些助手的设计选择，我建议您查看。

将下面的代码片段扩展到运行程序并在您自己的浏览器中验证结果 -

const likeList = (t = [], c = 0) =>
  ({ [Symbol.iterator]: _ => [ t[c], likeList(t, c + 1) ].values() })
  

const recur = (...v) =>
  ({ recur, [Symbol.iterator]: _ => v.values() })
  
const loop = (f, ...init) =>
{ let r = f(...init)
  while (r && r.recur === recur)
    r = f(...r)
  return r
}

const countTinyPairs = (a, b, k) =>
  loop
    ( ( [ x, xs ] = likeList(a)
      , [ y, ys ] = likeList([...b].reverse())
      , pairs = 0
      ) =>
      x == null || y == null
        ? pairs
        : recur
            ( xs
            , ys
            , Number(`${x}${y}`) < k
                ? pairs + 1
                : pairs
            )
    )
  
console.log(countTinyPairs([1,2,3,4,5], [3,4,5,6,7], 40))
// 3

这里还有优化的空间。这里我们介绍一下likeReversedList-

const likeReversedList = (t = [], c = 0) =>
  ({ [Symbol.iterator]: _ => [ t[t.length - c - 1], likeReversedList(t, c + 1) ].values() })

const countTinyPairs = (a, b, k) =>
  loop
    ( ( [ x, xs ] = likeList(a)
      , <del>[ y, ys ] = likeList([...b].reverse())</del>
      , [ y, ys ] = likeReversedList(b) // <-
      , pairs = 0
      ) =>
      // ...
    )

我如何在更短的时间内完成这个问题？

How would I complete this problem in less time?

javascript

big-o

消除 `a` 和 `b`

删除 `arr`

总结

备选

不丢弃重复项

`.map()` + `.filter()`

`.reduce()`

单个表达式`.reduce()`

我如何在更短的时间内完成这个问题？

How would I complete this problem in less time?

javascript

big-o

消除 a 和 b

删除 arr

总结

备选

不丢弃重复项

.map() + .filter()

.reduce()

单个表达式.reduce()

消除 `a` 和 `b`

删除 `arr`

`.map()` + `.filter()`

`.reduce()`

单个表达式`.reduce()`