有没有办法避免数字到字符串转换和嵌套循环以提高性能？

html5 • • 问答

我刚刚在网上进行了一次编码测试，这个问题真的让我很困扰。我的解决方案是正确的，但因未优化而被拒绝。问题如下：

编写一个combineTheGivenNumber带两个参数的函数：

  1. numArray： 数字[]
  2. num： 一个号码

该函数应该检查所有可能导致数字等于的连接对num并返回它们的计数。

例如，如果numArray= [1, 212, 12, 12]& num= 1212 那么我们将有3from 的返回值combineTheGivenNumber

对如下：

  1. numArray[0]+numArray[1]
  2. numArray[2]+numArray[3]
  3. numArray[3]+numArray[2]

我为此目的编写的函数如下：

function combineTheGivenNumber(numArray, num) {
  //convert all numbers to strings for easy concatenation
  numArray = numArray.map(e => e+'');
  //also convert the `hay` to string for easy comparison
  num = num+'';
  let pairCounts = 0;
  
  // itereate over the array to get pairs
  numArray.forEach((e,i) => {
    numArray.forEach((f,j) => {
    if(i!==j && num === (e+f)) {
        pairCounts++;
       }
    });
  });
  
  return pairCounts;
}

console.log('Test 1: ', combineTheGivenNumber([1,212,12,12],1212)); 

console.log('Test 2: ', combineTheGivenNumber([4,21,42,1],421));

回答

消除字符串到数字到字符串将显着提高速度

不，不会。

首先，您不会在任何地方将字符串转换为数字，但更重要的是，该练习要求连接，因此使用字符串正是您应该做的。不知道为什么他们甚至传递数字。通过为每个数字输入仅进行一次转换，而不是每次形成一对时，您已经做得很好了。最后但并非最不重要的一点是，避免转换不会有重大改进。

To get a significant improvement, you should use a better algorithm. @derpirscher is correct in his comment: "[It's] the nested loop checking every possible combination which hits the time limit. For instance for your example, when the outer loop points at 212 you don't need to do any checks, because regardless, whatever you concatenate to 212, it can never result in 1212".

So use

let pairCounts = 0;
numArray.forEach((e,i) => {
  if (num.startsWith(e)) {
//^^^^^^^^^^^^^^^^^^^^^^
    numArray.forEach((f,j) => {
      if (i !== j && num === e+f) {
        pairCounts++;
      }
    });
  }
});

You might do the same with suffixes, but it becomes more complicated to rule out concatenation to oneself there.

Optimising further, you can even achieve a linear complexity solution by putting the strings in a lookup structure, then when finding a viable prefix just checking whether the missing part is an available suffix:

function combineTheGivenNumber(numArray, num) {
  const strings = new Map();
  for (const num of numArray) {
    const str = String(num);
    strings.set(str, 1 + (strings.get(str) ?? 0));
  }
  const whole = String(num);
  
  let pairCounts = 0;
  for (const [prefix, pCount] of strings) {
    if (!whole.startsWith(prefix))
      continue;
    const suffix = whole.slice(prefix.length);
    if (strings.has(suffix)) {
      let sCount = strings.get(suffix);
      if (suffix == prefix) sCount--; // no self-concatenation
      pairCounts += pCount*sCount;
    }
  }
  return pairCounts;
}

(the proper handling of duplicates is a bit difficile)

以上是有没有办法避免数字到字符串转换和嵌套循环以提高性能？的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>
相关内容