java - 如何从Java中的数组中提取最长的连续整数序列？

Question

我想要的是显示给定的int数组中的所有连续序列。最后，我想用文本显示最长。

我尝试过的

• 我对数组进行了排序并找到了所有序列。
• 我将找到的序列存储到一个新的 ArrayList 中。

下面只是一小段代码，因为我知道其余的不起作用:

int[] myArray = {202,203,204,205,206, 100, 1, 3, 200, 2, 4, 201, 5};
ArrayList<Integer> secuence = new ArrayList<>();
Arrays.sort(myArray);

for (int i = 0; i < myArray.length - 1; i++) {
  if ((myArray[i] + 1) == myArray[i + 1] || (myArray[i] - 1) == myArray[i - 1]) {
    secuence.add(myArray[i]);
  }
}

我尝试了很多不同的方法，但无法弄清楚。

Answer 1

一些评论，建议:

• 由于 sort() 按升序对数组进行排序，实际上您不必检查递减的元素
• 为了查找“anything”est 事物，您需要存储迄今为止找到的“anything”est 事物以及当前候选者。这也适用于查找最大元素或最长的连续元素序列
• 为了处理数组的子部分，不需要创建元素的实际副本，存储开始索引和结束索引或长度就足够了。

将它们放在一起:

var myArray = [202,203,204,205,206, 100, 1, 3, 200, 2, 4, 201, 5];
myArray.sort((a,b)=>a-b);
console.log("Sorted array:",...myArray);

var longstart=0;
var longlength=0;

var currstart=0;
while(currstart<myArray.length){
  var currlength=0;
  while(currstart+currlength<myArray.length
    && myArray[currstart]+currlength==myArray[currstart+currlength])
    currlength++;
  if(currlength>longlength){
    longlength=currlength;
    longstart=currstart;
  }
  console.log("Sequence:",...myArray.slice(currstart,currstart+currlength));
  currstart+=currlength;
}
console.log("Longest:",...myArray.slice(longstart,longstart+longlength));

此代码是 JavaScript，因此可以在这里运行，Java 变体(只是打印较少)看起来非常相似:

int[] myArray = {202,203,204,205,206, 100, 1, 3, 200, 2, 4, 201, 5};
Arrays.sort(myArray);

int longstart=0;
int longlength=0;

int currstart=0;
while(currstart<myArray.length){
  int currlength=0;
  while(currstart+currlength<myArray.length
    && myArray[currstart]+currlength==myArray[currstart+currlength])
    currlength++;
  if(currlength>longlength){
    longlength=currlength;
    longstart=currstart;
  }
  currstart+=currlength;
}
for(int i=0;i<longlength;i++)
  System.out.print((i==0?"Longest: ":", ")+myArray[longstart+i]);

关键是要让检查随着距离的增加而工作，因此初始代码中的固定 [i]+1==[i+1] 检查变为 [i ]+距离==[i+距离]。