基于JavaScript，根据当前元素和前一个元素的差值对已排序数组进行分组

在给定的问题陈述中，我们必须利用JavaScript的功能，根据当前元素和前一个元素之间的差值对已排序数组进行分组。为了根据当前项和前一项之间的差值对已排序数组进行分组，我们可以遍历数组并创建一个新的分组数组。

理解问题陈述

上述问题陈述指出，我们必须根据数组中当前元素和前一个元素之间的差值找出元素组。由于我们得到的是一个已排序数组，因此我们需要根据每个元素与其前一个元素之间的差值对其元素进行分组。简单来说，每当连续元素之间的差值大于1时，我们就创建一个新的组。输出应该是一个分组数组，其中每个组包含连续元素之间的差值小于等于1的元素。

例如，假设我们有一个类似于[1, 2, 3, 5, 7, 9]的数组，那么我们将创建的函数应该输出[ [ 1, 2, 3 ], [ 5, 7, 9 ] ]。在这里我们可以看到1和2之间的差值为1，同样2和3之间的差值也是1。因此，考虑到相同的差值，我们将它们组合成一个组[1, 2, 3]。

算法

步骤1：为了解决根据当前元素和前一个元素之间的差值对已排序数组进行分组的给定问题，我们必须创建一个空数组来存储组。

步骤2：我们将使用一个变量来跟踪当前组。

步骤3：然后遍历已排序数组的元素，对于每个元素，我们将计算当前元素和前一个元素之间的差值。

步骤4：如果差值大于1，则创建一个新组并将当前元素包含在现有组中。

示例

//function to get the group array by difference
function groupByDiff(arr) {
   //Check if the provided array is empty 
   if (arr.length === 0) {
      return [];
   }
   //Initialize a variable to store the result
   const result = [];
   let currGroup = [arr[0]];

   for (let i = 1; i < arr.length; i++) {
      const diff = arr[i] - arr[i - 1];

      if (diff <= 1) {
         currGroup.push(arr[i]);
      } else {
         result.push(currGroup);
         currGroup = [arr[i]];
      }
   }

   result.push(currGroup);

   return result;
}

const sortedArray = [1, 2, 3, 5, 7, 9, 10, 14, 16, 17, 20, 21, 23];
const groupedArray = groupByDiff(sortedArray);

console.log(groupedArray);

输出

[
    [ 1, 2, 3 ], [ 5 ],
    [ 7 ],       [ 9, 10 ],
    [ 14 ],      [ 16, 17 ],
    [ 20, 21 ],  [ 23 ]
]

复杂度

提供的代码的时间复杂度为O(n)。这里n是数组中的元素个数。这种复杂度的原因是该函数遍历数组一次，并且对每个元素执行恒定时间操作。

在最坏情况下，代码的空间复杂度为O(m)。因为输入数组中的所有元素的差值都大于1，并且每个元素都在一个单独的组中，因此m等于输入数组的大小。如果元素之间的差值通常较小，则组的数量会更少。这里m是结果数组中组的数量。

结论

总之，该代码有效地根据连续元素之间的差值对已排序数组进行分组。它遍历数组一次，每当元素之间的差值大于1时就创建组。该代码提供了正确的元素分组，具有线性时间复杂度，使得代码高效。

更新于：2023年8月14日

390 次浏览

启动您的职业生涯

完成课程获得认证

开始
广告