我有一个按顺序排列的整数列表。我希望将连续整数组作为具有每组的第一个和最后一个整数的数组。
例如,对于(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
}
}
这段代码适用于我想要的一般情况,但是当最后一个序列只有1个整数时,它无法获得正确的结果。
例如,当使用此列表时:(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,所以我尝试了自己的编码。
试试这个
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]]
如果我理解你的问题,你可以写一个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]
我会指出,这是非常接近Run-length Encoding。
这是一个我有时会适应和使用的简单算法。
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+"]");
}
我想贡献一个用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")
}
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)
}
}
}