Leetcode #228. Summary Ranges

[yokostan]

Only beats 9%, two pointers:

class Solution {
    public List<String> res = new ArrayList<>();
    public List<String> summaryRanges(int[] nums) {
        if (nums == null || nums.length == 0) return res;

        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if ((long)nums[j] - (long)nums[j - 1] > 1) {
                getRange(nums, nums[i], nums[j - 1]);
                i = j;
            }
        }

        if (i < nums.length) getRange(nums, nums[i], nums[nums.length - 1]);

        return res;
    }

    private void getRange(int[] nums, int start, int end) {
        if (start == end) {
            res.add(String.valueOf(start));
            return ;
        }
        res.add(String.format("%d->%d", start, end));
    }
}

Binary Search:

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;

        int i = 0;
        int j = 0;
        while (i < nums.length) {
            j = getRangeEnd(nums, i, nums.length);
            if (i != j)
                res.add("" + nums[i] + "->" + nums[j]);
            else
                res.add("" + nums[i]);
            i = j + 1;
        }

        return res;
    }

    private int getRangeEnd(int[] nums, int start, int end) {
        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;
            if (nums[mid] == nums[start] + mid - start) {
                start = mid;
            }
            else end = mid;
        }
        return start;
    }
}

Here we should mind the binary search range (start and end point!)

[yokostan]

class Solution {
    public List<String> res = new ArrayList<>();
    public List<String> summaryRanges(int[] nums) {
        if (nums == null || nums.length == 0) return res;

        int i = 0;
        int j = 0;
        while (i < nums.length) {
            int start = i + 1, end = nums.length - 1;
            while (start + 1 < end) {
                int mid = (end - start) / 2 + start;
                if (nums[mid] <= nums[i] + mid - i) {
                    start = mid;
                }
                else end = mid;
            }
            if (nums[end] == nums[i] + end - i) {
                j = end;
            }
            else if (nums[start] == nums[i] + start - i) {
                j = start;
            }
            else j = i;
            // this case is super important
            //example: nums[0] = 0, nums[1] = 2, you can't find 
            //a number that satisfies the requirement
            //then you know i is gonna be alone
            //so we can set j = i and return "0" !!

            if (i != j)
                res.add("" + nums[i] + "->" + nums[j]);
            else
                res.add("" + nums[i]);
            i = j + 1;
        }

        return res;
    }
}