[LeetCode] 228. Summary Ranges

轉自LeetCode

Given a sorted integer array without duplicates, return the summary of its ranges.

Example 1:

Input:  [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range.

Example 2:

Input:  [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: 2,3,4 form a continuous range; 8,9 form a continuous range.

<Solution>

想法如下

• 因為是 sorted array，且沒有 duplicates，那麼如果是連續數字，則 index 的差值，就會等於 value 的差值

• 過程中，使用 binary search 的方式，來找到不是連續的數字

code 如下

Java(參考解法)

	class Solution {
	public List<String> summaryRanges(int[] nums) {
	final ArrayList<String> ans = new ArrayList<>();
	int idx = 0;
	int low, high, mid, last;
	while(idx < nums.length) {
	low = idx + 1;
	high = nums.length - 1;
	last = -1;
	while(low <= high) {
	mid = low + (high - low) / 2;
	if(nums[mid] - nums[idx] == mid - idx) {
	last = mid;
	low = mid + 1;
	} else {
	high = mid - 1;
	}
	}
	if(last == -1) {
	ans.add(String.valueOf(nums[idx++]));
	} else {
	ans.add(String.valueOf(nums[idx]) + "->" + String.valueOf(nums[last]));
	idx = last + 1;
	}
	}
	return ans;
	}
	}

view raw summaryRanges.java hosted with ❤ by GitHub