How to Summary Ranges using O(N) Two Pointer Algorithm?
- Time:2020-09-16 12:48:17
- Class:Weblog
- Read:37
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) —
Recommend:7 Ways to Enhance Your Blog with Video Advertising
California Consumer Privacy Act (CCPA) Compliance Guide For AdSe
What Is WordPress Live Chat and How Do You Implement It?
5 Beginner’s Tips to Building a WordPress Blog
8 Best Affiliate Marketing Plugins For Your Blog
How Many Squares/Rectangles Does a Rubik Cube Have?
Find the 10001st Prime Number
The Difference Between Sum of Squares and Square of the Sum
Number of Steps to Reduce a Number in Binary Representation to O
Recursive Depth First Search Algorithm to Compute the Diameter o
- Comment list
-
- Comment add