[LeetCode]Car Fleet

题目链接

很直观的题目，我们只需要把所有的car按照离target的距离从小到大排列，然后依次扫过去看当前的车和前面的fleet的第一辆车能否在到达target之前相遇，可以的话这两车就merge到前面的fleet。否则这辆车就成为新的fleet的第一辆车。时间复杂度的话就是sorting的时间复杂度O(n * log n)，空间复杂度O(n)，代码如下：

	class Solution {
	public:
	int carFleet(int target, vector<int>& position, vector<int>& speed) {
	int n = position.size();
	vector<int> idxs;
	for(int i = 0; i < n; ++i)idxs.push_back(i);
	auto comp = [&](const int& lhs, const int& rhs)
	{
	return position[lhs] > position[rhs];
	};
	sort(idxs.begin(), idxs.end(), comp);
	int fleets = 0, i = 0;
	while(i < n)
	{
	int idx = idxs[i], j = i + 1;
	long pos = position[idx], spd = speed[idx];
	//(target - pos[idxs[j]]) / speed[idxs[j]] <= (target - pos[idxs[i]]) / speed[idxs[i]]
	while(j < n && (target - position[idxs[j]]) * spd <= (target - pos) * speed[idxs[j]])++j;
	++fleets;
	i = j;
	}
	return fleets;
	}
	};

view raw Car Fleet.cpp hosted with ❤ by GitHub

这道题的follow up是在输入的基础上，如果有一辆跑的比其他车都快的车加入，可能在任何位置，输出结果集所有可能。其实仔细想一想不难理解，如果加在最前端，会多一个cluster，否则其前面的cluster的数量加一即可，也就是说所有其他cluster的数量都可以加一，输入所有结果即可。