N Car Fleet

Java

public class Solution {
    /**
     * @param target: the target
     * @param position: the initial position
     * @param speed: the speed
     * @return: How many car fleets will arrive at the destination
     */
		public int carFleet(int target, int[] position, int[] speed) {
			int n = position.length;
			int[][] cars = new int[n][2];
			for (int i = 0; i < n; i++) {
				cars[i][0] = position[i];
				cars[i][1] = speed[i];                            //双属性合并的套路
			}
			Arrays.sort(cars, (a, b) -> (b[0] - a[0])); //对比数组中的第一个数
			int res = 0;
			double maxTime = 0;
			for (int i = 0; i < n; i++) {
				double time = (double)(target - cars[i][0]) / cars[i][1];
				if (time > maxTime) {
					maxTime = time;
					res++;
				}
			}
			return res;
		}
}

Java

class Solution {
		public int carFleet(int target, int[] position, int[] speed) {
			int n = position.length; //how many cars total
			int[][] cars = new int[n][2]; //数组记录
			for (int i = 0; i < n; i++) {
				cars[i][0] = position[i]; //排序之前将车的位置记住，建立位置和速度的关系
				cars[i][1] = i;
			}
			Arrays.sort(cars, (a, b) -> (b[0] - a[0])); //sort by position to the target
			int res = 0;
			double maxTime = 0;
			for (int i = 0; i < n; i++) {
				double time = (double)(target - cars[i][0]) / speed[cars[i][1]];
				if (time > maxTime) {
					maxTime = time;
					res++;
				}
			}
			return res;
		}
}


Time Complexity : O(nlogn);
Space Complexity : O(n);