How to Summary Ranges using O(N) Two Pointer Algorithm?
- 时间:2020-09-16 12:48:17
- 分类:网络文摘
- 阅读:95 次
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.
Two Pointer Algorithm to Summary the Ranges
Since the array is already sorted, we can start scanning from left to the right, then continuously jump the pointer to the furthest if the next numbers are the neighbors. We then can generate the ranges for two cases: the single value (disjoint) or sub-ranges.
O(N) time and O(1) space requirement excluding the return vector. Each numbers in the array will be visited exactly once – the pointer will jump to the next range.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | class Solution { public: vector<string> summaryRanges(vector<int>& nums) { int i = 0, n = nums.size(); vector<string> r; while (i < n) { int j = i; while ((j + 1 < n) && (nums[j] + 1 == nums[j + 1])) j ++; if (i == j) { r.push_back(std::to_string(nums[i])); } else { r.push_back(std::to_string(nums[i]) + "->" + std::to_string(nums[j])); } i = j + 1; } return r; } }; |
class Solution { public: vector<string> summaryRanges(vector<int>& nums) { int i = 0, n = nums.size(); vector<string> r; while (i < n) { int j = i; while ((j + 1 < n) && (nums[j] + 1 == nums[j + 1])) j ++; if (i == j) { r.push_back(std::to_string(nums[i])); } else { r.push_back(std::to_string(nums[i]) + "->" + std::to_string(nums[j])); } i = j + 1; } return r; } };
We are using two pointers – the second pointer always is spawned from the first one. The above C++ solution implements this idea.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:过个文明的清明节作文 碎了的泪珠 春天的美作文200字 别走回头路,别翻旧事薄 大自然的风光作文400字 泥土 六一欢乐游园作文 永州韦使君新堂记原文及翻译 捕蛇者说原文及翻译 报孙会宗书原文及翻译
- 评论列表
-
- 添加评论