java - 按升序但有范围组织整数数组

Question

我得到一个整数数组:{3,2,5,1,7,10,9,12,11,14,15,13,​​20}。现在我需要对其进行排序(已经完成了)并将连续增加 1 的值分组，即将 "1,2,3" 转换为 "1 to 3" ，在“范围”内。

数组的预期输出，

{3,2,5,1,7,10,9,12,11,14,15,13,​​20}

应该是:

“1 到 3、5、7、9 到 15、20”

到目前为止我的解决方案是这样的:

//more code here
int[] a = new int[]{3,2,5,1,7,10,9,12,11,14,15,13,20};
String[] nSArr = new String[a.length];
String nStr = "";

for(int i=0; i<a.length; i++) {
    for(int j=i; j<a.length; j++) {
        if(a[j]==(a[i]+1)){
            nStr += Integer.toString(a[i])+","+Integer.toString(a[j])+" ";
        } else {
            nSArr[i] = a[i]+"";
        }
    }
}
//more code here

我计划将 nStr 转换为字符串数组，并使用重复的数字连接连续的数字，但这样做似乎很浪费。所以我的问题是，我应该用什么更好的方式存储连续的数字？

Answer 1

what better way should I store consecutive numbers?

你最好根本不存储它们。如果您必须生成范围列表，而不是打印它，您可以创建一个 Range 类，其中包含初始编号和运行长度等信息。单项运行的长度为 1，您可以通过返回 "7" 而不是 "7-7" 来打印结果。

以这种方式对项目进行分组的常见技巧是构造一个 (value[i] - i) 数字的并行数组，如下所示:

Value:    1  2  3  5  7  9 10 11 12 13 14 15 20
Index:    0  1  2  3  4  5  6  7  8  9 10 11 12
Diff:     1  1  1  2  3  4  4  4  4  4  4  4  8

您现在需要做的就是将具有相同 Diff 值的项目分组。这可以在单遍中完成，嵌套循环推进与外部循环相同的循环计数器，以获得 O(n) 时间解决方案。此外，您不需要显式存储 Diff，因此解决方案将是 O(1)-space:

int[] data = new int[] {3,2,5,1,7,10,9,12,11,14,15,13,20};
Arrays.sort(data);
int p = 0;
while (p != data.length) {
    System.out.print(data[p++]);
    int p0 = p;
    while (p != data.length && data[p-1]-(p-1) == data[p]-p) {
        p++;
    }
    if (p > p0+1) {
        System.out.print("-"+data[p-1]);
    } else {
        p = p0;
    }
    System.out.print(" ");
}

Demo.