Java：将int []转换为最小表示形式作为范围

Question

给定一个整数数组，如何将这个序列解析为计数序列表示法？

示例：

{1, 2, 3, 4, 5, 9, 13, 14, 15} -> "1-5,9,13-15"
{4, 6, 8, 10, 11, 12, 15, 17}  -> "4,6,8,10-12,15,17"

我希望能找到一种方法来产生这些结果。目前我已经有了以下代码，但是我在这一点上非常困惑：

测试代码：

import java.util.Arrays;
public class TestSequencing {
    public static void main(String[] args) {
        int[] numbers1 = {1, 2, 3, 4, 5, 9, 13, 14, 15};
        String numbers1s = "1-5,9,13-15";
        System.out.println(Arrays.toString(numbers1));
        System.out.println("Expected:\t" + numbers1s);
        System.out.println("Produced:\t" + sequenceNums(numbers1) + "\n");

        int[] numbers2 = {3, 5, 6, 9, 12};
        String numbers2s = "3,5-6,9,12";
        System.out.println(Arrays.toString(numbers2));
        System.out.println("Expected:\t" + numbers2s);
        System.out.println("Produced:\t" + sequenceNums(numbers2) + "\n");

        int[] numbers3 = {1, 2, 3, 4, 5, 6, 7};
        String numbers3s = "1-7";
        System.out.println(Arrays.toString(numbers3));
        System.out.println("Expected:\t" + numbers3s);
        System.out.println("Produced:\t" + sequenceNums(numbers3) + "\n");
    }

    public static String sequenceNums(int[] nums) {
        StringBuilder sb = new StringBuilder();
        int rangeStart = nums[0];
        int previous = nums[0];
        int current;
        int expected = previous + 1;

        for (int i = 1 ; i < nums.length ; i++) {
            current = nums[i];
            expected = previous + 1;               
            if (current != expected || i == (nums.length - 1)) {
                if (current == rangeStart) {
                    sb.append(previous + ",");
                } else {
                    sb.append(rangeStart + "-" + previous + ",");
                }                
                rangeStart = current;
            }              
            previous = current;
        }
        if (sb.charAt(sb.length() - 1) == ',') {
            sb.deleteCharAt(sb.length() - 1);
        }
        return sb.toString();
    }
}

输出：

[1, 2, 3, 4, 5, 9, 13, 14, 15]
Expected:   1-5,9,13-15
Produced:   1-5,9-9,13-14

[3, 5, 6, 9, 12]
Expected:   3,5-6,9,12
Produced:   3-3,5-6,9-9

[1, 2, 3, 4, 5, 6, 7]
Expected:   1-7
Produced:   1-6

- user4996976

---

@SotiriosDelimanolis，请给出建设性的评论。我的预期结果已经清楚地阐明了，我提供的示例表明了我的代码没有产生我正在寻求的结果。 - user4996976

我问你为什么它没有做你想要的事情。你调试过了吗？你发现了什么？ - Sotirios Delimanolis

@SotiriosDelimanolis 我猜问题与数组中缺少最后一个数字有关。我尝试了使用其他控制流结构的不同想法，但是我已经没有办法解决它了。我提供的示例是我解决问题的最接近方法，因此我在这里发布希望从新思维中获得新的想法。 - user4996976

我发现这是一个更好的编程使用案例。可能是一个面试问题！ - JavaHopper

@N99x 修复了你的代码。如果有任何情况失败，请告诉我。 - JavaHopper

Answer 1

试试这个：

private static void appendRange(StringBuilder sb, int begin, int end) {
    sb.append(",").append(begin);
    if (end != begin)
        sb.append("-").append(end);
}

public static String sequenceNums(int[] nums) {
    StringBuilder sb = new StringBuilder();
    if (nums.length == 0) return sb.toString();
    int begin = nums[0], end = nums[0];
    for (int cur : nums)
        if (cur - end <= 1)
            end = cur;
        else {
            appendRange(sb, begin, end);
            begin = end = cur;
        }
    appendRange(sb, begin, end);
    return sb.substring(1);
}

@Test
public void testSequenceNums() {
    assertEquals("1-5,9,13-15", sequenceNums(new int[] {1, 2, 3, 4, 5, 9, 13, 14, 15}));
    assertEquals("4,6,8,10-12,15,17", sequenceNums(new int[] {4, 6, 8, 10, 11, 12, 15, 17}));
    assertEquals("1-7", sequenceNums(new int[] {1, 2, 3, 4, 5, 6, 7}));
    assertEquals("", sequenceNums(new int[] {}));
}

- user4910279

Answer 2

我采用下面的方法来表示整数数组的范围。

注意：数字应该按升序预先排序。

我们将使用两个变量start和current在迭代中识别范围。 index是数组的当前索引。

找到范围后，我们将继续将其推入StringBuilder中。

这是代码：

// We will take this set of integers 
int[] temp = new int[] { 0, 1, 4, 5, 8, 9, 11, 12, 13 };

// Helper variables
Integer start = null, current = null;

// The found range(s) will be stored in this variable.
StringBuilder rangeBuilder = new StringBuilder();

// The current index of the array in iteration
int index = 0;

do {
    // During the first iteration both start & current will be null. So setting the current index value to them.
    if (start == null) {
        start = current = temp[index];
    } else {
        // Checking if the index value is the next number of current.
        if (temp[index] == (current + 1)) {
            current = temp[index];
        } else {
            if (start == current) {
                rangeBuilder.append(start + ",");
            } else {
                rangeBuilder.append(start + "-" + current + ",");

            }
            start = current = temp[index];
        }

    }

    // Checking if we have reached the end of the array.
    if (index + 1 == temp.length) {
        if (start == current) {
            rangeBuilder.append(start);
        } else {
            rangeBuilder.append(start + "-" + current);
        }
    }

} while (index++ < temp.length - 1);

// Printing the range.
System.out.println("Range: " + rangeBuilder.toString());

解释：

我们以这个例子为例：

{ 0, 1, 4, 5, 8, 9, 11, 12, 13 }

注意：我们将表示起始点为s，当前点为c

迭代-1：

输入：起始点 = null，当前点 = null，范围生成器 = ""

sc
0,  1,  4,  5,  8,  9,  11,  12, 13
^

索引值是当前数字的下一个吗？不是

索引是否已经到达最后一个元素？不是

退出：起始值=0，当前值=0，范围生成器=""

迭代-2：

进入：起始值=0，当前值=0，范围生成器=""

s   c
0,  1,  4,  5,  8,  9,  11,  12, 13
    ^

索引值是当前数字的下一个数字吗？是的。所以我们将 c 从 0 移动到 1 。

索引是否已经到达最后一个元素？不

退出：start = 0，current = 1，rangeBuilder =“”

迭代-3：

输入：start = 0，current = 1，rangeBuilder =“”

        sc
0,  1,  4,  5,  8,  9,  11,  12, 13
        ^

索引值是“当前”数字的下一个吗？不是。因此，我们将s和c推入字符串生成器（rangeBuilder）。在推送时，我们检查s和c是否相同以避免重复。然后，我们将s和c移动到索引值。

索引是否已达到最后一个元素？没有。

退出：start = 4，current = 4，rangeBuilder =“0-1，”

迭代-4：

输入：start = 4，current = 4，rangeBuilder =“0-1，”

        s   c
0,  1,  4,  5,  8,  9,  11,  12, 13
            ^

索引值是“当前”数字的下一个数字吗？是的。所以我们将“c”从“4”移动到“5”。

索引是否已经到达最后一个元素？没有

退出：start = 4，current = 5，rangeBuilder =“0-1，”

迭代-5：

进入：start = 4，current = 5，rangeBuilder =“0-1，”

                sc
0,  1,  4,  5,  8,  9,  11,  12, 13
                ^

索引值是“当前”数字的下一个吗？不是。因此，我们将s和c推入字符串生成器（rangeBuilder）。在推送时，我们检查s和c是否相同以避免重复。然后，我们将s和c移动到索引值。

索引是否已达到最后一个元素？没有。

退出：start = 8，current = 8，rangeBuilder =“0-1,4-5,”

迭代-6：

进入：start = 8，current = 8，rangeBuilder =“0-1,4-5,”

                s   c
0,  1,  4,  5,  8,  9,  11,  12, 13
                    ^

索引值是“当前”数字的下一个数字吗？是的。所以我们将“c”从“8”移动到“9”。

索引是否已经到达最后一个元素？没有

退出：start = 8，current = 9，rangeBuilder =“0-1,4-5,”

迭代-7：

输入：start = 8，current = 9，rangeBuilder =“0-1,4-5,”

                        sc
0,  1,  4,  5,  8,  9,  11,  12, 13
                        ^

索引值是当前数字的下一个吗？不是。所以我们将s和c推入字符串生成器（rangeBuilder）。在推送时，我们检查s和c是否相同，以避免重复。然后我们将s和c移动到索引值。

索引是否已经到达最后一个元素？没有。

退出：start = 11，current = 11，rangeBuilder =“0-1,4-5,8-9,”

迭代-8：

进入：start = 11，current = 11，rangeBuilder =“0-1,4-5,8-9,”

                        s    c
0,  1,  4,  5,  8,  9,  11,  12, 13
                             ^

索引值是当前数字的下一个吗？是的。因此，我们将c从11移动到12。

索引是否已达到最后一个元素？不是。

退出：start = 11，current = 12，rangeBuilder = "0-1,4-5,8-9,"

迭代-9：

进入：start = 11，current = 12，rangeBuilder = "0-1,4-5,8-9,"

                        s        c
0,  1,  4,  5,  8,  9,  11,  12, 13
                                 ^

索引值是“当前”数字的下一个数字吗？是的。所以我们将“c”从“12”移动到“13”。

索引是否已经到达最后一个元素？是的。所以我们将“s”和“c”推入字符串生成器（rangeBuilder）。在推送时，我们检查“s”和“c”是否相同，以避免重复。

迭代结束。字符串生成器（rangerBuilder）将具有此值：0-1,4-5,8-9,11-13

请随意改进此代码 :)

- Sathieswar

Answer 3

在for循环中，你有两个问题：

1）第二个if应该是if (previous == rangeStart) { 2）你没有处理循环中的最后一个数字（其中i == (nums.length - 1)）。

我会使用以下代码来解决这个问题：

public static String sequenceNums(int[] nums) {
    StringBuilder sb = new StringBuilder();

    int rangeStart = nums[0];
    int previous = nums[0];
    int current;
    int expected = previous + 1;
    int size = nums.length;

    for (int i = 1 ; i < size ; i++) {
        current = nums[i];
        expected = previous + 1;

        if (current != expected) {
            addRange(sb, rangeStart, previous);
            rangeStart = current;
        }

        previous = current;
    }
    addRange(sb, rangeStart, nums[size - 1]);

    return sb.toString();
}

private void addRange(StringBuilder sb, int from, int to) {
    if (sb.length() > 0) {
        sb.append(",");
    }
    if (from == to) {
        sb.append(from);
    } else {
        sb.append(from + "-" + to);
    }
}

- DuncanKinnear

Answer 4

这是您修复后的代码。

public class TestSequencing {

    public static void main(String[] args) {
        int[] numbers1 = {1, 2, 3, 4, 5, 9, 13, 14, 15};
        String numbers1s = "1-5,9,13-15";
        System.out.println(Arrays.toString(numbers1));
        System.out.println("Expected:\t" + numbers1s);
        System.out.println("Produced:\t" + sequenceNums(numbers1) + "\n");

        int[] numbers2 = {3, 5, 6, 9, 12};
        String numbers2s = "3,5-6,9,12";
        System.out.println(Arrays.toString(numbers2));
        System.out.println("Expected:\t" + numbers2s);
        System.out.println("Produced:\t" + sequenceNums(numbers2) + "\n");

        int[] numbers3 = {1, 2, 3, 4, 5, 6, 7};
        String numbers3s = "1-7";
        System.out.println(Arrays.toString(numbers3));
        System.out.println("Expected:\t" + numbers3s);
        System.out.println("Produced:\t" + sequenceNums(numbers3) + "\n");
    }

    public static String sequenceNums(int[] nums) {
        StringBuilder sb = new StringBuilder();
        int rangeStart = nums[0];
        int previous = nums[0];
        int current;
        int expected = previous + 1;

        for (int i = 1 ; i < nums.length ; i++) {
            current = nums[i];
            expected = previous + 1;               
            if (current != expected || i == (nums.length - 1)) {
                if (current == rangeStart) {
                    sb.append(previous + ",");
                } else {
                    if(rangeStart != previous) {
                        if(i == nums.length - 1)
                            sb.append(rangeStart + "-" + current);
                        else
                            sb.append(rangeStart + "-" + previous + ",");
                    } else {
                        if(i == nums.length - 1)
                            sb.append(rangeStart + "," + current);
                        else
                            sb.append(rangeStart + ",");
                    }
                }                
                rangeStart = current;
            }              
            previous = current;
        }
        if (sb.charAt(sb.length() - 1) == ',') {
            sb.deleteCharAt(sb.length() - 1);
        }
        return sb.toString();
    }

}

问题在于，如果当前值与范围起始值不同，则需要检查两种情况。
1）如果范围以相同的前一个值开头。如果是这样，则不需要将相同的数字分隔开（例如：9-9没有意义，只有9）。还要处理的另一种情况是到达数组结尾。如果到达数组结尾，则应将其添加到末尾，即使它不属于任何范围。
2）否则，如果未达到数组结尾，则范围以前一个值开始和结束。如果到达数组结尾，则为范围的结束值。

- JavaHopper

---

谢谢您的解释！ 我将@saka1029的答案标记为已接受，因为我喜欢他的代码简洁高效，但是您的回答更加详细和有教育意义。 - user4996976

Answer 5

我通过引入一个布尔标志并重新设计方法以测试连续数字来解决了您的问题。如果当前和下一个数字是连续的，则会触发inRangeFlag以进行下一次迭代。请参见下面的代码注释以获取更详细的说明：

   public static String sequenceNums(int[] nums) {

    StringBuilder sb = new StringBuilder();
    int current;
    int next;
    boolean inRangeFlag = false;

    for (int i = 0; i < nums.length; i++) {

        current = nums[i];

        // TRUE: if element is not last element, because last number is
        // always appended.
        if (i < nums.length - 1) {

            next = nums[i + 1];

            // TRUE: if current element and next are consecutive
            if (next - current == 1) {

                // If rangeflag is false, the current number is the start
                // of a range. Append the number with hyphen.
                if (!inRangeFlag) {
                    sb.append(current + "-");
                }

                // Trigger inRange Flag for next iteration.
                inRangeFlag = true;

            } else {
                sb.append(current + ",");
                inRangeFlag = false; // Turn flag false because not inRange.
            }
        } else {
            sb.append(current);
        }
    }
    return sb.toString();
}

- AngelTrs