LC.P2251[花期内花的数目]

方法一：排序+二分查找

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
class Solution {
    public int[] fullBloomFlowers(int[][] flowers, int[] people) {
        int n = flowers.length;
        int[] starts = new int[n], ends = new int[n];
        for (int i = 0; i < n; ++i) {
            starts[i] = flowers[i][0];
            ends[i] = flowers[i][1];
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        for (int i = 0; i < people.length; ++i) {
            people[i] = binarySearch(starts, people[i] + 1) - binarySearch(ends, people[i]);
        }
        return people;
    }

    private int binarySearch(int[] nums, int x) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + right >>> 1;
            if (nums[mid] >= x) right = mid;
            else left = mid + 1;
        }
        return right;
    }
}
  • 时间复杂度：$O((n + m)logn)$，其中$n$为$flowers$的长度，$m$为$people$的长度
  • 空间复杂度：$O(n)$

方法二：排序+差分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] fullBloomFlowers(int[][] flowers, int[] people) {
        TreeMap<Integer, Integer> d = new TreeMap<>();
        for (int[] flower : flowers) {
            d.merge(flower[0], 1, Integer::sum);
            d.merge(flower[1] + 1, -1, Integer::sum);
        }
        int sum = 0, m = people.length;
        Integer[] idx = new Integer[m];
        for (int i = 0; i < m; ++i) {
            idx[i] = i;
        }
        Arrays.sort(idx, (a, b) -> people[a] - people[b]);
        int[] ans = new int[m];
        for (int i : idx) {
            int p = people[i];
            while (!d.isEmpty() && d.firstKey() <= p) {
                sum += d.pollFirstEntry().getValue();
            }
            ans[i] = sum;
        }
        return ans;
    }
}
  • 时间复杂度：$O(mlogn + nlogn)$
  • 空间复杂度：$O(m + n)$