【笔试题】提取区域

今天笔试遇到这样一个题！

提取区域

一个有序的整数列表示方式通常使用逗号隔开。
如果序列中的几个整数是连续递增1时，可以使用数字范围的方式表达，通常用“-”符隔开。而“-”的两端分别表示此数据范围的起始数据和结束数据（包括起始数据和结束数据），如果想使用区域的表达方式必须保证区域中至少有3个整数。例如：12,13,15-17

此任务会提供一个有序的整数列表，你需要编写函数按上述描述将此列表进行格式化。

【解】

当时想到了这样的解法通过了：

遍历数组，用一个List来临时保存一下递增1的子序列，当遇到下一个不是递增1时，对List中的数据，根据数据个数是否达到3个进行处理，要么使用“-”隔开表示范围，要么一一列出。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = new int[]{-3, -2, -1, 1, 2, 3, 4, 5, 9, 10, 22, 23, 24, 25, 30};
        String ans = Solution.rangeExtraction(arr);
        System.out.println(ans); // -3--1,1-5,9,10,22-25,30
    }
}

class Solution {
    public static String rangeExtraction(int[] arr) {
        if (arr == null || arr.length == 0) {
            return "";
        }
        int n = arr.length;
        StringBuilder res = new StringBuilder();
        if (n < 3) {
            for (int a : arr) {
                res.append(a).append(",");
            }
            return res.substring(0, res.length() - 1);
        }
        List<Integer> tmp = new ArrayList<>();
        tmp.add(arr[0]);
        for (int i = 1; i < n; i++) {
            int cur = arr[i];
            if (cur != tmp.get(tmp.size() - 1) + 1) {
                process(tmp, res);
                tmp.clear();
            }
            tmp.add(cur);
        }
        if (tmp.size() > 0) {
            process(tmp, res);
        }
        return res.substring(0, res.length() - 1);
    }

    private static void process(List<Integer> tmp, StringBuilder res) {
        if (tmp.size() >= 3) {
            res.append(tmp.get(0)).append("-").append(tmp.get(tmp.size() - 1)).append(",");
        } else {
            for (int a : tmp) {
                res.append(a).append(",");
            }
        }
    }
}

后来想到用两根指针来写，时间复杂度一样是O(n)，但是空间减少了一个List的开销，并且代码更简洁。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = new int[]{-3, -2, -1, 1, 2, 3, 4, 5, 9, 10, 22, 23, 24, 25, 30};
        String ans = Solution.rangeExtraction(arr);
        System.out.println(ans); // -3--1,1-5,9,10,22-25,30
    }
}

class Solution {
    public static String rangeExtraction(int[] arr) {
        if (arr == null || arr.length == 0) {
            return "";
        }
        int n = arr.length;
        StringBuilder res = new StringBuilder();
        int start = 0, end = 1;
        while (end <= n) {
            if (end == n || arr[end] != arr[end - 1] + 1) {
                if (end - start >= 3) {
                    res.append(arr[start]).append("-").append(arr[end - 1]).append(",");
                    start = end;
                } else {
                    while (start < end) {
                        res.append(arr[start]).append(",");
                        start++;
                    }
                }
            }
            end++;
        }
        return res.substring(0, res.length() - 1);
    }
}