leetcode 683 K Empty Slots

Posted on | In |

题目大意：有n个花盆，第i天，第flowers[i]个花盆的花会开。问是否存在一天，两朵花之间有k个空花盆。

There is a garden with N slots. In each slot, there is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly one flower blooming and it will be in the status of blooming since then.

Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day.

For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x, where i and x will be in the range from 1 to N.

Also given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming.

If there isn’t such day, output -1.

Example 1:

Input:

flowers: [1,3,2]

k: 1

Output: 2

Explanation: In the second day, the first and the third flower have become blooming.

Example 2:

Input:
flowers: [1,2,3]

k: 1

Output: -1

Note:

The given array will be in the range [1, 20000].
Idea:

BST/Buckets

可以直接暴力写 时间复杂度O(2nk)
对于第i天的花 遍历左边k个元素都是slots 第k+1个是花 则返回
或者 遍历右边k个元素都是slots 第k+1个是花 则也返回

法一 (o (nlogn))

set有序插入

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
//有序插入的思想 
//集合set中元素都是有序的
#include<iostream>
#include<vector>
#include<set>
#include<queue>
using namespace std;
int kEmptySlots(vector<int>& flowers, int k) {
	int n=flowers.size();
		
	set<int> s;
	for(int i=0;i<n;i++){
		int num=flowers[i];
		auto r=s.insert(flowers[i]).first;
		auto l=r;
		//如果set后面有元素 
		if(++r!=s.end()&&*r==num+k+1) return i+1;
		if((l--)!=s.begin()&&*l==num-k-1) return i+1;
	}
	return -1;
	} 
	
int main(){
	
	vector<int> flowers;
	flowers.push_back(1); 
	flowers.push_back(3);
	flowers.push_back(2);  
	int k=1;
	int t=kEmptySlots(flowers,k);
	cout<<t<<endl;
	
	
	return 0;
}

bucket思想

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
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
int n,k;
int kEmptySlots(vector<int>& flowers, int k) {
	int n=flowers.size();
	//int	bs=ceil(n/k+1);
	int bs=(n+k)/(k+1);
		vector<int> lower(bs,INT_MAX);
		vector<int> higher(bs,INT_MIN);		
		for(int i=0;i<n;i++){
			int dui=flowers[i]/(k+1);
			if(flowers[i]<lower[dui]) {
				lower[dui]=flowers[i];
				if(dui>0&&higher[dui-1]==flowers[i]-k-1) 
		       	return i+1;	
			}
			if(flowers[i]>higher[dui]){
				higher[dui]=flowers[i];
				if(dui<bs-1&&lower[dui+1]==flowers[i]+k+1) return i+1;	
				
			}
			
		}
	return -1;
	
	} 
		
int main(){
	
	
	vector<int> flowers;
	flowers.push_back(1); 
	flowers.push_back(3);
	flowers.push_back(2);  
	int k=1;
	int t=kEmptySlots(flowers,k);
	cout<<t<<endl;
}