javascript - Codewars "Closest and Smallest"- 与预期输出不匹配

Question

我为 Codewars 5kyu 挑战 Closest and Smallest 编写了以下代码。

Input

• a string strng of n positive numbers (n = 0 or n >= 2) Let us call weight of a number the sum of its digits. For example 99 will have "weight" 18, 100 will have "weight" 1.

Two numbers are "close" if the difference of their weights is small.

Task:

For each number in strng calculate its "weight" and then find two numbers of strng that have:

• the smallest difference of weights ie that are the closest
• with the smallest weights
• and with the smallest indices (or ranks, numbered from 0) in strng

Output:

• an array of two arrays, each subarray in the following format:

  [number-weight, index in strng of the corresponding number, original
  corresponding number in strng]
  

The two subarrays are sorted in ascending order by their number weights if these weights are different, by their indexes in the string if they have the same weights.

我在 Node 中使用 Jest 在本地进行测试 - 一切正常。
但它没有通过 Codewars 的测试。我真的很感激这方面的任何提示。谢谢!

function closest(string) {
  if (string.length < 1)
    return [];
  const nums = string.split(" ");
  const weights = nums.map(e => e.split('').reduce((p, a) => Number(p) + Number(a)));
  const indexedWeights = [];
  let indexCounter = 0;
  for (let w of weights)
    indexedWeights.push([w, indexCounter++, Number(nums.shift())])
  let collected = [];
  indexedWeights.forEach(iw => {
    const iWCopy = indexedWeights.filter(item => item !== iw);
    const closest = iWCopy.reduce((a, b) => Math.abs(b[0] - iw[0]) < Math.abs(a[0] - iw[0]) ? b : a);
    const diff = Math.abs(closest[0] - iw[0]);
    collected.push([diff, iw[0], iw[1], iw[2]]);
  });
  collected.sort((a, b) => a[0] - b[0])
  const lowestDiff = collected[0][0]
  const result = collected.filter(n => n[0] === lowestDiff)
  result.sort((a, b) => a[1] - b[1])
  return [result[0].splice(1, 4), result[1].splice(1, 4)];
}

测试:

const closest = require("../5kyu_challenges/closestAndSmallest");
describe("closest", () => {
  test("returns an array containing 2 sub-arrays which consist of 3 numbers representing closest and smallest numbers", () => {
    expect(closest("")).toEqual([]);
    expect(closest("456899 50 11992 176 272293 163 389128 96 290193 85 52")).toEqual([ [13, 9, 85], [14, 3, 176] ]);
  });
  test("sorts by index number if weights are equal", () => {
    expect(closest("239382 162 254765 182 485944 134 468751 62 49780 108 54")).toEqual([ [8, 5, 134], [8, 7, 62] ]);
    expect(closest("403749 18 278325 97 304194 119 58359 165 144403 128 38")).toEqual([ [11, 5, 119], [11, 9, 128] ]);
  });
});

Answer 1

要求也按匹配的索引对输出进行排序(我突出显示):

The two subarrays are sorted in ascending order by their number weights if these weights are different, by their indexes in the string if they have the same weights.

所以在你的代码中改变这一行:

result.sort((a, b) => a[1] - b[1])

用这个:

result.sort((a, b) => a[1] - b[1] || a[2] - b[2])

效率

请注意，排序的时间复杂度为 O(nlogn)。因此，如果输入是一个非常大的数组，与扫描 collected 数组以获取最小值相比，对 collected 进行排序可能是一个较差的解决方案。