CODEWITHSUNDEEP
javaarraysstring
Helquin
Helquin

Reputation: 188

Organizing an Integer Array in Ascending Order but with Ranges

I'm given an Integer Array that goes: {3,2,5,1,7,10,9,12,11,14,15,13,20}. Now I need to sort it(already done this) and group the values that increase by 1 consecutively, i.e. convert "1,2,3" to "1 to 3", in a "range".

With that the expected output from the array,

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

shoul be:

"1 to 3, 5, 7, 9 to 15, 20"

My solution so far is this:

//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

I'm planning on converting nStr into a String Array and using the duplicated numbers to connect consecutive numbers, but doing that seems to be wasteful. So my question is that, what better way should I store consecutive numbers?

Upvotes: 1

Views: 149

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726839

what better way should I store consecutive numbers?

You would be better off not storing them at all. If you have to produce a list of ranges, rather than printing it, you could create a Range class that has, for example, the initial number and the length of the run. Single-item runs would have length of one, which you could use in printing the result by returning "7" instead of "7-7".

A common trick for grouping items this way is to construct a parallel array of (value[i] - i) numbers, like this:

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

All you need to do now is to group items with identical value of Diff. This can be done in a single pass, with the nested loop advancing the same loop counter as the outer loop for an O(n)-time solution. Moreover, you don't need to store Diff explicitly, so the solution would be 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.

Upvotes: 1

Related Questions