853. 车队【力扣】

题目链接： 853. 车队
难度：中等



说实话，这个题我开始看了半天都不太知道要干啥，最后看了看题解，才自己写出来的。

class Solution {
	//因为交换麻烦，所以写了个swap的方法
    public static void swap(double cars[][],int i,int j){
        double[][] tmp = new double[1][2];
        tmp[0][0] = cars[i][0];
        tmp[0][1] = cars[i][1];
        cars[i][0] = cars[j][0];
        cars[i][1] = cars[j][1];
        cars[j][0] = tmp[0][0];
        cars[j][1] = tmp[0][1];

    }
    //排序麻烦，写了个冒泡排序算法，其实用快排啥的写也可以，二维数组的一个快排
    //写的这个没有用，效率不高
    public static void sort(double cars[][],int size){
        for(int i = 0;i<size;i++){
            boolean flag = false;
            for(int j = 1;j<size-i;j++){
                if(cars[j][0] < cars[j-1][0]){
                    swap(cars,j,j-1);
                    flag = true;
                }
            }
            if(!flag)
                return;
        }

    }

    public int carFleet(int target, int[] position, int[] speed) {
        //计算出所需要的时间，将位置与时间放到一个double的二维数组中
        int n = speed.length;
        if(n<=1){
            return n;
        }
        double[][] cars = new double[n][2];
        for(int i = 0;i < n;i++){
            cars[i][0] = position[i];
            cars[i][1] = (double)(target-position[i])/speed[i];
        }
        //按位置，升序排列
        // sort(cars,n); 
        Arrays.sort(cars,Comparator.comparingDouble(a->a[0])); //还是直接调用的sort算法
        //找到有多少个车队
        //位置近，时间长的，会被位置远，时间短的追上组成一个车队。
        //位置近，时间短的，会自己组成一个车队
        int ret = 0;
        double maxTime = cars[n-1][1];
        for(int i = n-1; i >= 1; i--){
            if(maxTime < cars[i-1][1]){
                ret++;
                maxTime = cars[i-1][1];
            }
        }
        //最后的一个车队
        ret++;
        return ret;
    }
}
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