LeetCode/Java/881.java at master · strengthen/LeetCode · GitHub

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
60
61
62
63
__________________________________________________________________________________________________
sample 3 ms submission
class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int count = 0;
        int left = 0;
        int right = limit;
        int[] bucket = new int[limit + 1];
        for (int p : people) bucket[p]++;

        while (left <= right) {
            while (left <= right && bucket[left] <= 0) left++;
            while (left <= right && bucket[right] <= 0) right--;

            if (left > right) {
               break;
            }
            // if (bucket[left] <= 0 && bucket[right] <= 0) {
            //     break;
            // }
            if (left + right <= limit) {
                bucket[left]--;
            }
            bucket[right]--;
            count++;
        }
        return count;
    }
}
__________________________________________________________________________________________________
sample 47872 kb submission
class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int[] array = new int[limit + 1];
        for(int person: people){
            array[person]++;
        }
        int l = 1, r = limit;
        int ret = 0;
        while(r >= l){
            if(array[l] == 0){
                l++;
            }else if(array[r] == 0){
                r--;
            }else if(r + l <= limit){
                if(r == l){
                    ret += array[r] / 2 + array[r] % 2;
                    break;
                }else{
                    int min = Math.min(array[r], array[l]);
                    array[r] -= min;
                    array[l] -= min;
                    ret += min;
                }
            }else{
                ret += array[r];
                r--;
            }
        }
        return ret;
    }
}
__________________________________________________________________________________________________