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

Question

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

• 我对数组进行了排序，找到了所有序列

以下仅是一小段代码，因为我知道其余部分不起作用：

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

我的解决方案如下：

1. 一个连续的序列（我们要找到的）是至少2个连续的整数s（对）
的 List
2. 要返回所有查找序列，您需要一个结果List包含0个或多个Lists
3. 要检查连续性，您需要当前和先前元素

应用的逻辑（如果）：

1. 如果当前==前1，则找到连续性，否则现有的连续序列被破坏
2. 如果一个序列至少有2个元素，即sequence.size（）

迭代元素（循环）：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class ConsecutiveSequenceFinder {

    private int[] unsortedNumbers;

    public ConsecutiveSequenceFinder(int[] numbers) {
        this.unsortedNumbers = numbers;
    }

    public int[] sorted() {
        int[] sortedNumbers = Arrays.copyOf(this.unsortedNumbers, this.unsortedNumbers.length);
        Arrays.sort(sortedNumbers);
        return sortedNumbers;
    }

    public List<List<Integer>> findSequences() {
        // one sequence is List of integers; thus list of sequences is list of list of integers
        List<List<Integer>> foundSequences = new ArrayList<>();
        // first we sort the array
        int[] ascending = this.sorted();
        // this working variable will hold the currently found sequence
        List<Integer> sequence = new ArrayList<Integer>();
        Integer previous = null;
        System.out.println("Finding sequences ..");
        for (int current : ascending) {
            // check if current value is first or one more than (consecutive to) previous
            if (previous == null || current == previous + 1) {
                sequence.add(current);
                previous = current;
            } else {
                System.out.printf("\tsequence of %d consecutive is broken at: %d\n", sequence.size(), current);
                // if sequence found (at least a pair) then add
                if (sequence.size() > 1) {
                    foundSequences.add(sequence);
                }
                // and finally prepare a new sequence, to collect fresh again
                sequence = new ArrayList<>();
                previous = null;
            }
        }
        // if sequence left, then add
        if (sequence.size() > 1) {
            System.out.printf("\tsequence of %d consecutive was completed with last array element\n", sequence.size());
            foundSequences.add(sequence);
        }
        return foundSequences;
    }

    public static void main (String[] args) throws java.lang.Exception {
        // demo numbers
        int[] values = {202,203,204,205,206, 100, 1, 3, 200, 2, 4, 201, 5};
        // starting demo
        System.out.println("Input: " + Arrays.toString(values));
        ConsecutiveSequenceFinder finder = new ConsecutiveSequenceFinder(values);
        System.out.println("Sorted: " + Arrays.toString(finder.sorted()));
        List<List<Integer>> foundSequences = finder.findSequences();
        System.out.println("Found sequences: " + foundSequences.size());
        // print for each sequence the size and its elements
        for (List<Integer> sequence : foundSequences) {
            System.out.printf("\t %d elements: %s\n",sequence.size(), sequence.toString());
        }
        // check for each sequence if it is the longest
        List<Integer> longestSequence = new ArrayList<>();
        for (List<Integer> sequence : foundSequences) {
            if (sequence.size() > longestSequence.size()) {
                longestSequence = sequence;
            }
        }
        System.out.printf("Longest sequence has %d elements: %s\n",longestSequence.size(), longestSequence.toString());
    }
}

Input: [202, 203, 204, 205, 206, 100, 1, 3, 200, 2, 4, 201, 5]
Sorted: [1, 2, 3, 4, 5, 100, 200, 201, 202, 203, 204, 205, 206]
Finding sequences ..
    sequence of 5 consecutive is broken at: 100
    sequence of 7 consecutive was completed with last array element
Found sequences: 2
     5 elements: [1, 2, 3, 4, 5]
     7 elements: [200, 201, 202, 203, 204, 205, 206]
Longest sequence has 7 elements: [200, 201, 202, 203, 204, 205, 206]

Process finished with exit code 0

Answer 2

几句评论、建议：

• 由于排序（）按递增顺序对数组排序，实际上不必检查递减元素
• 为了找到“任何”最重要的东西，您需要存储迄今为止找到的“任何”最重要的东西，以及当前的候选对象。这也适用于查找最大元素或连续元素的最长序列
• 对于处理数组的子部分，不必制作元素的实际副本，只需存储开始索引和结束索引或长度即可

将它们放在一起：

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));