我怎样才能在更短的时间内完成这个问题？

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，则这样的一对称为“微小”。”

这是我写的代码：

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

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

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

消除aand的多个循环b

假设 和a的b长度相等，我们可以用一个循环简单地迭代两个数组。为了实现反向迭代，我们可以使用基本算术来获得与末尾距离相同的索引 for和 hasb的索引与开头的距离相同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. 根据规范，查找和插入将具有次线性复杂性。许多实现甚至可以为您提供O(1). 您可以将代码简化为

const pairs = new Set();

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

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

概括

完整的解决方案可能如下所示，您只需要同时迭代a一次b：

const pairs = new Set();

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

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

选择

这也可以使用数组方法来表达，从而缩短代码，但需要使用.mapand进行两个循环.filter，然后将第三个循环转换为 a Set：

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));

使用.reduce它再次将其降至一个循环：

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));

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

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));

或者使用数组方法：

.map()+.filter()

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));

.reduce()

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));