时间戳

首页 > 解决方案 > 在未排序的数组中查找所有非连续数对

javascript - 在未排序的数组中查找所有非连续数对

问题描述

给定一个未排序的数组，需要得到所有非连续元素对。

Input [2,3,4,5,9,8,10,13]
Desired output (2,5)(8,10)(13,13)

解释：

Input = [2,3,4,5,9,8,10,13]

如果我们按给定数组的递增顺序创建序列，那么它将是：

[2,3,4,5,8,9,10,13]

现在，如果分解为序列中断的组：

[2,3,4,5]
[8,9,10]
[13]

然后，输出将是组的第一个和最后一个数字，如果组中只有一个数字，那么它将被视为快速和最后一个。

输出：

[2,5][8,10][13,13]

我的解决方法：

var array = [2,3,4,5,9,8,10,13]
var input = array.sort((a,b)=>{return a-b});
var group = [];
var start = input[0];
for(let i = 0; i<input.length; i++){
    if(input[i+1] - input[i] > 1){
        group.push([start,input[i]])
        start = input[i+1];
    }
}
console.log(group);

输出：

[ [ 2, 5 ], [ 8, 10 ] ]

标签： javascriptarraysalgorithm

解决方案

我的方法

这是一个完全按照您上面建议的步骤的实现。首先我们在sort数字上。然后我们用reduce它把它分解成一组连续的数字。然后我们map将该结果中的数组取为第一个和最后一个值。

因为我们将多次需要它，所以我们编写了一个简单的辅助函数，last以获取数组中的最终元素。

const last = (xs) => 
  xs [xs .length - 1]

const nonConsecutives = (ns) =>
  [...ns] 
    .sort ((a, b) => a - b) 
    .reduce (
      (r, n, i) => (i == 0 || n > last (last (r)) + 1)
        ? r .concat ([[n]])
        : r .slice (0, -1) .concat ([last (r) .concat (n)]),
      []
    ) 
    .map (ns => [ns [0], last (ns)])


console .log (
  nonConsecutives ([2, 3, 4, 5, 9, 8, 10, 13])
)

修正你的方法

如果您更想知道您的方法哪里出错了，那么问题出在边界上（在许多编程中经常如此！）该行if (input [i + 1] - input [i] > 1)最后会出现问题i，因为不会有input [i + 1]. 同样，您不希望start = input [i + 1]在第一次迭代时执行此更新。

这个类似的版本似乎有效。我们在当前索引和前一个索引之间进行测试。（我们还添加了一个预先检查当前索引是0，这在技术上不是必需的，因为input [i] - input [i - 1]会产生input [i] - undefined，这是NaN，并且NaN > 1是错误的，所以我们无法进入if语句的主体。但是，虽然在技术上不是必需的，它更干净。）我们不会在第一个索引上推送新组，但在循环完成后，我们会推送最后一个组。

这是一个实现：

const array = [2, 3, 4, 5, 9, 8, 10, 13]
const input = array .sort ((a, b) => a - b)
const group = []
let start = input [0]
for (let i = 0; i < input .length; i++){
    if (i == 0 || input [i] - input [i - 1] > 1) {
        if  (i > 0) {
          group .push ([start, input [i - 1]])
        }
        start = input [i]
    }
}
group .push ([start, input [input .length - 1]])

console.log(group);

差异

这里的方法差异很大。当然，一个是我将我的操作包装在一个函数中。那些喜欢函数式编程的人几乎总是会这样做。另一个是我将我的构建为一系列不同的转换。我通常会更明确地这样做（更多内容见下文），但这里仍然很清楚：首先我们排序，然后我们分组，然后我们捕获端点。这通常不是最有效的方法，但通常是最清晰的。

最大的不同是，在我的版本中，我们不会沿途改变任何变量，只会创建新变量。（甚至在reduce回调中也是如此，尽管有时性能问题会让我在这里选择其他方式。）这是函数式编程的核心原则：永远不要改变输入数据。

使用 Ramda

我是Ramda函数式编程库的创始人之一。它有许多有用的辅助函数；它是围绕简单转换管道的概念设计的，它们都不会改变它们的数据。在 Ramda 中，我们可以更简单地这样写：

const {pipe, sortBy, identity, groupWith, map, juxt, head, last} = R

const nonConsecutives = pipe (
  sortBy (identity),
  groupWith ((a, b) => b - a <= 1),
  map (juxt ([head, last]))
)

console .log (
  nonConsecutives ([2, 3, 4, 5, 9, 8, 10, 13])
)
<script src="//cdnjs.cloudflare.com/ajax/libs/ramda/0.27.1/ramda.min.js"></script>

我不会详细介绍它是如何工作的。而且我并不想出售 Ramda。但想法是，将问题分解为更小的问题可以生成非常干净的代码。如果您可以在纯函数中捕获这些较小的部分，那么您就可以很好地进行函数式编程。

推荐阅读