How to Summary Ranges using O(N) Two Pointer Algorithm?
- 时间:2020-09-16 12:48:17
- 分类:网络文摘
- 阅读:97 次
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) —
推荐阅读:Recursive Depth First Search Algorithm to Compute the Sum of Nod How to Convert Integer to the Sum of Two No-Zero Integers? Algorithm to Generate the Spiral Matrix in Clock-wise Order How to Remove the Duplicates from Sorted List (Leaving Only Dist How to Sort a Linked List by Converting to Array/Vector? Know The Effective and Smart SEO Reporting Tool You Must Use Pro Content Marketing Tips You Can Implement NOW 8 WordPress Plugins for Better User Experience 6 Eye-Opening Tips for Measuring and Improving the Impact of You Should a Professional Blog Be Funny?
- 评论列表
-
- 添加评论