-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsummary_ranges.h
More file actions
executable file
·73 lines (61 loc) · 1.87 KB
/
Copy pathsummary_ranges.h
File metadata and controls
executable file
·73 lines (61 loc) · 1.87 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/*
Author: cuckoo
Date: 2017/05/08 20:34:43
Update:
Problem: Summary Ranges
Difficulty: Medium
Source: https://leetcode.com/problems/summary-ranges/#/description
*/
#include <vector>
using std::vector;
#include <string> // for to_string()
using std::string;
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
return summaryRangesFirst(nums);
}
vector<string> summaryRangesFirst(vector<int>& nums)
{
vector<string> result;
int n = nums.size(), start = 0, end = 0;
while(end < n)
{
start = end;
++end;
while(end < n && nums[end] - nums[end - 1] == 1)
++end;
string temp = std::to_string(nums[start]);
if(end - 1 != start)
temp += "->" + std::to_string(nums[end - 1]);
result.push_back(std::move(temp));
}
return result;
}
int BinarySearch(vector<int> &nums, int low, int high)
{
while(low + 1 < high)
{
int mid = low + (high - low) / 2;
if(nums[mid] - nums[low] == mid - low)
low = mid;
else
high = mid;
}
return low;
}
vector<string> summaryRangesSecond(vector<int>& nums)
{
vector<string> result;
int n = nums.size(), k = 0;
for(int i = 0; i < n; i = k + 1)
{
k = BinarySearch(nums, i, n);
if(i != k)
result.push_back(std::to_string(nums[i]) + "->" + std::to_string(nums[k]));
else
result.push_back(std::to_string(nums[i]));
}
return result;
}
};