How to Summary Ranges using O(N) Two Pointer Algorithm?
- Time:2020-09-16 12:48:17
- Class:Weblog
- Read:32
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:5 Healthy Lifestyle Blogs to Know This 2020
Young People Changing the World One Idea at a Time
Remember Your Blog Is A Reflection Of You
Learn About Blog Content Planning
Adding PHPUnit Tests for Discord Cryptocurrency Bot Regarding th
Algorithm to Multiply Two Big Integers (String)
Use jQuery Migrate Helper Plugin to Fix the Classic Editor Error
How to Fix CloudFlare Error 1101 (Worker threw exception)?
Python Function to Convert Excel Sheet Column Titles to Numbers
Algorithm to Find the Kth Missing Positive Number in Array
- Comment list
-
- Comment add