在Java中查找列表中连续整数的组

Question

我有一组按顺序排列的整数列表。

我希望能够将连续的整数分组为具有每组第一个和最后一个整数的数组。

例如，对于 (2,3,4,5,8,10,11,12,15,16,17,18,25) ，我想得到一个包含这些数组的列表：[2,5]、[8,8]、[10,12]、[15,18]、[25,25]。

下面是我的代码：

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


public class MyRangesTest {


public static void main(String[] args) {
    //create list of integers
    List<Integer> list=Arrays.asList(2,3,4,5,8,10,11,12,15,16,17,18,25);
    System.out.println("list:" + list);


        //create a list with integers where a new sequense of consecutive integers starts or ends
        List<Integer> sublistsStarsAndEnds= new ArrayList<>();
        sublistsStarsAndEnds.add(list.get(0));//1st line (always in sublistsStarsAndEnds list)
        for (int i=1; i<list.size()-1; i++){
            if (list.get(i)>1+list.get(i-1)){
                sublistsStarsAndEnds.add(list.get(i-1));
                sublistsStarsAndEnds.add(list.get(i));
            }
        }
        sublistsStarsAndEnds.add(list.get(list.size()-1));//last line (always in sublistsStarsAndEnds list)
        System.out.println("sublistsStarsAndEnds: " + sublistsStarsAndEnds);//present the result


        //create list with arrays that represents start and end of each subrange of consequent integers
        List<Integer[]> ranges= new ArrayList<>();
        for (int i=0; i<sublistsStarsAndEnds.size()-1; i=i+2){
            Integer[] currentrange=new Integer[2];
            currentrange[0]=sublistsStarsAndEnds.get(i);
            currentrange[1]=sublistsStarsAndEnds.get(i+1);
            ranges.add(currentrange);//present the result
        }

        //present the result
        String rangestxt="";//create result text
        for (int i=0; i<ranges.size(); i++){
            rangestxt=rangestxt+ranges.get(i)[0]+ " " + ranges.get(i)[1]+ "    ";
         }        
        System.out.println("ranges: " + rangestxt);//present the result


    }

}

这段代码通常符合我的需求，但是当最后一组序列只有一个整数时，它无法得到正确的结果。

例如，当使用此列表：(2,3,4,5,8,10,11,12,15,16,17,18,25) 时，我们得到的范围不是 [2,5] [8,8] [10,12] [15,18] [25,25]，而是 [2,5] [8,8] [10,12] [15,25]。

问题出在检测范围开始或结束的位置上。在我的代码中，这些地方存储在sublistsStarsAndEnds 列表中。这里，我们得到的不是[2, 5, 8, 8, 10, 12, 15, 15, 25, 25]，而是 [2, 5, 8, 8, 10, 12, 15, 25]。

我尝试过修正代码，但没有好的结果。

请问有什么建议吗？

附言：有人想要得到我想要的结果，并在Python中提出了一个问题，链接在此 "Identify groups of continuous numbers in a list"，但是我不懂Python，所以我尝试自己编写代码。

- geo

Answer 1

尝试这个

 public static void main(String[] args) {
    List<Integer> list=Arrays.asList(2,3,4,5,8,10,11,12,15,16,17,18,19,25);
    List<List<Integer>>lList=new ArrayList<List<Integer>>(); //list of list of integer
    System.out.println("list:" + list);
    int i=0;
    int start=0;
        List<Integer> sList=new ArrayList<Integer>(2);
        for(  i = 1; i <list.size();i++){

           if( list.get(i - 1) + 1 != list.get(i)){
               sList.add(list.get(start));
               sList.add(list.get(i-1));
               lList.add(sList);
               sList=new ArrayList<Integer>(2);
               start=i;

            }

        }
        sList.add(list.get(start));        // for last range
        sList.add(list.get(list.size()-1));
        lList.add(sList);


    System.out.println("Range :"+lList);
}

输出：

list:[2, 3, 4, 5, 8, 10, 11, 12, 15, 16, 17, 18, 19, 25]
Range :[[2, 5], [8, 8], [10, 12], [15, 19], [25, 25]]

- Rustam

Answer 2

如果我理解你的问题，你可以编写一个POJO类Range，如下所示：

static class Range {
    private int start;
    private int end;

    Range(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public String toString() {
        return String.format("%d - %d", start, end);
    }
}

那么你的问题变成了在一个结束位置添加一个 start，其中结束位置是 i-1 在 list.get(i - 1) + 1 != list.get(i)。像这样：

public static void main(String[] args) {
    List<Integer> list = Arrays.asList(2, 3, 4, 5, 8, 10, 11, 12, 15, 16,
            17, 18, 25);
    System.out.println("list:" + list);
    int start = 0;
    List<Range> ranges = new ArrayList<>();
    for (int i = 1; i < list.size(); i++) {
        if (list.get(i - 1) + 1 != list.get(i)) {
            ranges.add(new Range(list.get(start), list.get(i - 1)));
            start = i;
        }
    }
    ranges.add(new Range(list.get(start), list.get(list.size() - 1)));
    System.out.println(ranges);
}

输出结果（按要求）为：

[2 - 5, 8 - 8, 10 - 12, 15 - 18, 25 - 25]

我想指出这几乎是一种类似于游程编码的技术。

- Elliott Frisch

Answer 3

简单优雅的解决方案：

    static String pair(int[] array){
        String res = "";
        
        int i = 0, j = 1;
        //loop through all items in array.
        while(i < array.length){
            //increase j while array[j] - array[j - 1] equals 1
            while(j < array.length && array[j] - array[j - 1] == 1){
                j++;
            }
            //we came out of that loop, no longer in a sequence. 
            //write to the output.
            res += toTuple(i,j - 1, array);
            //i now points to j.
            //j is now i + 1;
            i = j;
            j = i + 1;
        }
    
        return res;
    }
    
    static String toTuple(int low, int high, int[] array){
        return "[" + array[low] + "," + array[high] + "]";
    }

• 示例输入：{1, 2, 3, 6, 7,9,10,11,13,14,15,20}
• 输出结果：[1,3][6,7][9,11][13,15][20,20]

注意：本文是关于 IT 技术的翻译，涉及到代码和格式，翻译时请仔细核对。

- Rafael Valle

Answer 4

在 Kotlin 中的另一个简短答案，假设列表中没有重复项。

    list.fold(mutableListOf<MutableList<Int>>()) { acc, i ->
        acc.also { outer ->
            outer.lastOrNull()?.takeIf { it[1] + 1 == i  }?.also {
                it[1] = i
            } ?: mutableListOf(i, i).also {
                outer.add(it)
            }
        }
    }

- jfawkes

Answer 5

我想贡献一个用Kotlin编写的解决方案：

@Test
fun test_extract_continuous_range() {
    val inputList = listOf(0, 2, 3, 4, 5, 8, 10, 11, 12, 15, 16, 17, 18, 19, 25, 26, 27, 30)
    println("Input:  $inputList")

    val result = mutableListOf<IntRange>()
    result.add(inputList.first()..inputList.first()) // add the first item as the first range
    inputList.windowed(2)
        .map { w -> w.first() to w.second() } // optional map to Pair for convenient
        .forEach { p ->
            if (p.first + 1 == p.second) {
                // same range, extend it
                val updatedLastRange = result.last().start..p.second
                result[result.lastIndex] = updatedLastRange
            } else {
                // new range
                result.add(p.second..p.second)
            }
        }

    println("Result: $result")

    val sizes = result.map(IntRange::count)
    println("Sizes:  $sizes")
}

- Hoang Tran

Answer 6

这是一个我有时会改编和使用的简单算法。

public void printRanges(int[] input) {
    if (input.length == 0)
        return;

    // Only necessary if not already sorted
    Arrays.sort(input);

    int start = input[0];
    int end = input[0];

    for (int rev : input) {
        if (rev - end > 1) {
            // break in range
            System.out.println("Range: [" + start + ", " + end + "]");
            start = rev;
        }
        end = rev;
    }
    System.out.println("Range: [" + start + ", " + end+"]");
}

- triadiktyo