https://leetcode.com/contest/leetcode-weekly-contest-51/problems/k-empty-slots/
[Implementation idea]:
[1st method]:
1. Make an array A which array index is the position & array value is the blooming day.2. Check if there is a pair (A[x], A[x+k+1]) such that max(A[n], A[n+k+1]) > all of the values of A[x], x = n+1, ... ,n+k, A[x] is the values between [min(A[n], A[n+k]), max(A[n], A[n+k])]
3. After scanning all candidates of step 2, if have NOT found one, return -1.
4. Otherwise, return the minimum of all candidate pairs: (max(A[n], A[n+k+1])).
A. Complexity is O(N*k) if a native comparison is applied.
B. Complexity is O(N*log(k)) if a
B.1: C++ STL set can be used directly as a handy solution.
we need to remove from set. As the result, the data structure should have following properties.
1. Support query max & min in O(1) => begin() & rbegin()
2. Support delete a specific element in O(logn) => erase()
3. Support add a specific element in O(logn) => insert()
#include <iostream>
#include <limits.h>
#include <list>
#include <vector>
#include <algorithm>
#include <set>
#include <time.h>
using namespace std;
class Solution {
void dumpSet(set<int> &in) {
set<int>::iterator it;
for (it = in.begin(); it != in.end(); it++) {
cout << ((*it == INT_MAX) ? -1 : (*it)) << ", ";
}
cout << "\n";
}
public:
int kEmptySlots(vector<int>& flowers, int k) {
int minDay = INT_MAX;
/*boundary condition*/
if ((k < 0) || (k > (flowers.size() - 2)))
return -1;
vector<int> day(flowers.size(), -1);
for (int i = 0; i < flowers.size(); i++) {
day[flowers[i] - 1] = (i + 1);
}
set<int> between;
between.insert(INT_MAX);
int start = 0;
int end = (start + k + 1);
int max;
for (int i = 1; i <= k; i++) {
between.insert(day[i]);
}
while (end < flowers.size()) {
max = (day[start] > day[end]) ? day[start] : day[end];
if (minDay > max) {
int betweenMin = *(between.begin());
if (betweenMin > max) {
minDay = max;
}
}
between.insert(day[end]);
end++;
start++;
between.erase(day[start]);
}
cout << "minDay = " << minDay << "\n";
if (minDay == INT_MAX)
return -1;
else
return minDay;
}
};
int main() {
srand(unsigned(time(0)));
vector<int> testVector;
int ret;
testVector.clear();
// set some values:
for (int i = 1; i <= 10; ++i)
testVector.push_back(i);
// using built-in random generator:
random_shuffle(testVector.begin(), testVector.end());
// print out content:
if (0)
for (vector<int>::iterator it = testVector.begin(); it != testVector.end(); ++it)
cout << *it << ", ";
cout << "\n";
Solution sol;
ret = sol.kEmptySlots(testVector, 5);
cout << ret << '\n';
return 0;
}
[2nd better method]:
1st Solution does not utilize the information during check fully.
It means:
[A[n], A[n+1], A[n+2], ...., A[n+t], ... A[n+k+1]]
when we find A[n+t] > max(A[n], A[n+k+1]) at t, if means all values from:
[A[n+1], A[n+2], ...., A[n+t -1]] satisfies
[A[n+1], A[n+2], ...., A[n+t -1]] < max(A[n], A[n+k+1]) < A[n+t] .
Hence they are IMPOSSIBLE to be the candidate so we can skip them directly.
It means the next check range is from A[n+t] to A[n+t + k +1] if it is legal.
So we can save the time to check the range which starts from A[n+1], A[n+2], ...., A[n+t -1].
Furthermore, notice that A[n+t+1], ..., A[n+k] have NOT been probed yet, it means to maintain the min heap as method 1 is unnecessary.
Following program shows the faster implementation.
The experimental result is given also to show the difference on speed when k is large.
#include <iostream>
#include <limits.h>
#include <list>
#include <vector>
#include <algorithm>
#include <set>
#include <time.h>
using namespace std;
class Solution {
void dumpSet(set<int> &in) {
set<int>::iterator it;
for (it = in.begin(); it != in.end(); it++) {
cout << ((*it == INT_MAX) ? -1 : (*it)) << ", ";
}
cout << "\n";
}
public:
int kEmptySlots(vector<int>& flowers, int k) {
int minDay = INT_MAX;
/*boundary condition*/
if ((k < 0) || (k > (flowers.size() - 2)))
return -1;
vector<int> day(flowers.size(), -1);
for (int i = 0; i < flowers.size(); i++) {
day[flowers[i] - 1] = (i + 1);
}
set<int> between;
between.insert(INT_MAX);
int start = 0;
int end = (start + k + 1);
int max;
for (int i = 1; i <= k; i++) {
between.insert(day[i]);
}
while (end < flowers.size()) {
max = (day[start] > day[end]) ? day[start] : day[end];
if (minDay > max) {
int betweenMin = *(between.begin());
if (betweenMin > max) {
minDay = max;
}
}
between.insert(day[end]);
end++;
start++;
between.erase(day[start]);
}
cout << "end = " << end << "\n";
cout << "minDay = " << minDay << "\n";
if (minDay == INT_MAX)
return -1;
else
return minDay;
}
};
class Solution2 {
public:
int kEmptySlots(vector<int>& flowers, int k) {
vector<int> days(flowers.size());
for(int i = 0; i < flowers.size(); i++)
days[flowers[i] - 1] = i + 1;
int left = 0;
int right = k + 1;
int res = INT_MAX;
for(int i = 0; right < days.size(); i++){
if(days[i] < days[left] || days[i] <= days[right]){
if(i == right)
res = min(res, max(days[left], days[right])); //we get a valid subarray
left = i, right = k + 1 + i;
}
}
return (res == INT_MAX)? -1 :res;
}
};
int main() {
srand(unsigned(time(0)));
vector<int> testVector;
int ret1;
int ret2;
testVector.clear();
// set some values:
for (int i = 1; i <= 1000000; ++i)
testVector.push_back(i);
// using built-in random generator:
random_shuffle(testVector.begin(), testVector.end());
// print out content:
if (0)
for (vector<int>::iterator it = testVector.begin(); it != testVector.end(); ++it)
cout << *it << ", ";
cout << "\n";
Solution sol;
Solution2 sol2;
clock_t begin = clock();
ret1 = sol.kEmptySlots(testVector, 300000);
clock_t end = clock();
double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
cout << "method 1: ans = " << ret1 << " execution time = " << time_spent << '\n';
begin = clock();
ret2 = sol2.kEmptySlots(testVector, 300000);
end = clock();
time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
cout << "method 1: ans = " << ret2 << " execution time = " << time_spent << '\n';
return 0;
}
The speed is O(n) versus O(n*2*logk).
留言
張貼留言