花期内花的数目

2251. 花期内花的数目

给你一个下标从 0 开始的二维整数数组 flowers ，其中 flowers[i] = [start_i, end_i] 表示第 i 朵花的花期从 start_i 到 end_i （都包含）。同时给你一个下标从 0 开始大小为 n 的整数数组 persons ，persons[i] 是第 i 个人来看花的时间。

请你返回一个大小为 n 的整数数组 answer ，其中 answer[i]是第 i 个人到达时在花期内花的数目。

示例 1：

输入：flowers = [[1,6],[3,7],[9,12],[4,13]], persons = [2,3,7,11]
输出：[1,2,2,2]
解释：上图展示了每朵花的花期时间，和每个人的到达时间。
对每个人，我们返回他们到达时在花期内花的数目。

示例 2：

输入：flowers = [[1,10],[3,3]], persons = [3,3,2]
输出：[2,2,1]
解释：上图展示了每朵花的花期时间，和每个人的到达时间。
对每个人，我们返回他们到达时在花期内花的数目。

提示：

1 <= flowers.length <= 5 * 10⁴
flowers[i].length == 2
1 <= start_i <= end_i <= 10⁹
1 <= persons.length <= 5 * 10⁴
1 <= persons[i] <= 10⁹

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) { } };

javascript 解法, 执行用时: 224 ms, 内存消耗: 74.3 MB, 提交时间: 2023-09-28 07:42:30

/**
 * @param {number[][]} flowers
 * @param {number[]} persons
 * @return {number[]}
 */
var fullBloomFlowers = function (flowers, people) {
    const diff = new Map();
    for (const [start, end] of flowers) {
        diff.set(start, (diff.get(start) ?? 0) + 1);
        diff.set(end + 1, (diff.get(end + 1) ?? 0) - 1);
    }
    const times = [...diff.keys()].sort((a, b) => a - b);

    const id = [...people.keys()].sort((i, j) => people[i] - people[j]);
    let j = 0, sum = 0;
    for (const i of id) {
        while (j < times.length && times[j] <= people[i]) {
            sum += diff.get(times[j++]); // 累加不超过 people[i] 的差分值
        }
        people[i] = sum; // 从而得到这个时刻花的数量
    }
    return people;
};

rust 解法, 执行用时: 44 ms, 内存消耗: 7 MB, 提交时间: 2023-09-28 07:42:14

use std::collections::BTreeMap;

impl Solution {
    pub fn full_bloom_flowers(flowers: Vec<Vec<i32>>, people: Vec<i32>) -> Vec<i32> {
        let mut diff = BTreeMap::new();
        for f in &flowers {
            *diff.entry(f[0]).or_insert(0) += 1;
            *diff.entry(f[1] + 1).or_insert(0) -= 1;
        }

        let n = people.len();
        let mut id: Vec<usize> = (0..n).collect();
        id.sort_by(|&i, &j| people[i].cmp(&people[j]));

        let mut ans = vec![0; n];
        let mut it = diff.iter().peekable();
        let mut sum = 0;
        for &i in &id {
            while let Some((&t, &d)) = it.peek() {
                if t > people[i] {
                    break;
                }
                sum += d; // 累加不超过 people[i] 的差分值
                it.next();
            }
            ans[i] = sum; // 从而得到这个时刻花的数量
        }
        ans
    }
}

java 解法, 执行用时: 54 ms, 内存消耗: 70.2 MB, 提交时间: 2023-09-28 07:41:38

class Solution {
    public int[] fullBloomFlowers(int[][] flowers, int[] people) {
        int[] starts = Arrays.stream(flowers).mapToInt(f -> f[0]).sorted().toArray();
        int[] ends = Arrays.stream(flowers).mapToInt(f -> f[1]).sorted().toArray();
        return Arrays.stream(people).map(p -> lowerBound(starts, p + 1) - lowerBound(ends, p)).toArray();
    }

    // 返回 >= x 的第一个数的下标
    // 如果不存在（所有元素都小于 x），则返回 nums.length
    private int lowerBound(int[] nums, int x) {
        int left = -1, right = nums.length; // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // nums[left] < x
            // nums[right] >= x
            int mid = left + (right - left) / 2;
            if (nums[mid] < x) {
                left = mid; // 区间缩小为 (mid, right)
            } else {
                right = mid; // 区间缩小为 (left, mid)
            }
        }
        return right; // 根据循环不变量，此时 right 就是满足 nums[right] >= x 的最小值
    }
}

javascript 解法, 执行用时: 220 ms, 内存消耗: 74.1 MB, 提交时间: 2023-09-28 07:41:19

/**
 * @param {number[][]} flowers
 * @param {number[]} persons
 * @return {number[]}
 */
var fullBloomFlowers = function (flowers, people) {
    const starts = flowers.map(f => f[0]).sort((a, b) => a - b);
    const ends = flowers.map(f => f[1]).sort((a, b) => a - b);
    return people.map(p => lowerBound(starts, p + 1) - lowerBound(ends, p));
};

// 返回 >= x 的第一个数的下标
// 如果不存在（所有元素都小于 x），则返回 nums.length
var lowerBound = function (nums, x) {
    let left = -1, right = nums.length; // 开区间 (left, right)
    while (left + 1 < right) { // 区间不为空
        // 循环不变量：
        // nums[left] < x
        // nums[right] >= x
        const mid = left + ((right - left) >> 1);
        if (nums[mid] < x)
            left = mid; // 区间缩小为 (mid, right)
        else
            right = mid; // 区间缩小为 (left, mid)
    }
    return right; // 根据循环不变量，此时 right 就是满足 nums[right] >= x 的最小值
};

rust 解法, 执行用时: 48 ms, 内存消耗: 6.6 MB, 提交时间: 2023-09-28 07:40:55

impl Solution {
    pub fn full_bloom_flowers(flowers: Vec<Vec<i32>>, people: Vec<i32>) -> Vec<i32> {
        let mut starts: Vec<i32> = flowers.iter().map(|f| f[0]).collect();
        let mut ends: Vec<i32> = flowers.iter().map(|f| f[1]).collect();
        starts.sort();
        ends.sort();
        people.iter().map(|&p| Solution::lower_bound(&starts, p + 1) - Solution::lower_bound(&ends, p)).collect()
    }

    fn lower_bound(nums: &Vec<i32>, x: i32) -> i32 {
        let mut left = 0;
        let mut right = nums.len();
        while left < right {
            let mid = left + (right - left) / 2;
            if nums[mid] < x {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        left as i32
    }
}

golang 解法, 执行用时: 200 ms, 内存消耗: 13.9 MB, 提交时间: 2023-06-13 14:22:02

func fullBloomFlowers(flowers [][]int, persons []int) []int {
	diff := map[int]int{}
	for _, f := range flowers {
		diff[f[0]]++
		diff[f[1]+1]--
	}

	n := len(diff)
	times := make([]int, 0, n)
	for t := range diff {
		times = append(times, t)
	}
	sort.Ints(times)

	for i, p := range persons {
		persons[i] = p<<32 | i
	}
	sort.Ints(persons)

	ans := make([]int, len(persons))
	i, sum := 0, 0
	for _, p := range persons {
		for ; i < n && times[i] <= p>>32; i++ {
			sum += diff[times[i]] // 累加变化量
		}
		ans[uint32(p)] = sum
	}
	return ans
}

golang 解法, 执行用时: 172 ms, 内存消耗: 11.9 MB, 提交时间: 2023-06-13 14:21:47

func fullBloomFlowers(flowers [][]int, persons []int) []int {
	n := len(flowers)
	starts := make([]int, n)
	ends := make([]int, n)
	for i, f := range flowers {
		starts[i] = f[0]
		ends[i] = f[1]
	}
	sort.Ints(starts)
	sort.Ints(ends)

	ans := make([]int, len(persons))
	for i, p := range persons {
		ans[i] = sort.SearchInts(starts, p+1) - sort.SearchInts(ends, p)
	}
	return ans
}

java 解法, 执行用时: 70 ms, 内存消耗: 61 MB, 提交时间: 2023-06-13 14:21:34

class Solution {
    public int[] fullBloomFlowers(int[][] flowers, int[] persons) {
        var diff = new HashMap<Integer, Integer>();
        for (var f : flowers) {
            diff.put(f[0], diff.getOrDefault(f[0], 0) + 1);
            diff.put(f[1] + 1, diff.getOrDefault(f[1] + 1, 0) - 1);
        }
        var times = diff.keySet().stream().mapToInt(Integer::intValue).sorted().toArray();

        var n = persons.length;
        var ids = IntStream.range(0, n).boxed().toArray(Integer[]::new);
        Arrays.sort(ids, (i, j) -> persons[i] - persons[j]);

        var ans = new int[n];
        int i = 0, sum = 0;
        for (var id : ids) {
            while (i < times.length && times[i] <= persons[id])
                sum += diff.get(times[i++]); // 累加变化量
            ans[id] = sum;
        }
        return ans;
    }
}

java 解法, 执行用时: 45 ms, 内存消耗: 71.3 MB, 提交时间: 2023-06-13 14:21:20

class Solution {
    public int[] fullBloomFlowers(int[][] flowers, int[] persons) {
        var starts = Arrays.stream(flowers).mapToInt(f -> f[0]).sorted().toArray();
        var ends = Arrays.stream(flowers).mapToInt(f -> f[1]).sorted().toArray();
        return Arrays.stream(persons).map(p -> lowerBound(starts, p + 1) - lowerBound(ends, p)).toArray();
    }

    int lowerBound(int[] arr, int x) {
        int left = 0, right = arr.length;
        while (left < right) {
            var mid = (left + right) >>> 1;
            if (arr[mid] >= x) right = mid;
            else left = mid + 1;
        }
        return left;
    }
}

python3 解法, 执行用时: 160 ms, 内存消耗: 39.7 MB, 提交时间: 2023-06-13 14:21:07

# 转换 + 二分
class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], persons: List[int]) -> List[int]:
        starts = sorted(s for s, _ in flowers)
        ends = sorted(e for _, e in flowers)
        return [bisect_right(starts, p) - bisect_left(ends, p) for p in persons]

python3 解法, 执行用时: 256 ms, 内存消耗: 37.8 MB, 提交时间: 2023-06-13 14:20:45

# 差分
class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], persons: List[int]) -> List[int]:
        diff = defaultdict(int)  # 也可以用 SortedDict
        for start, end in flowers:
            diff[start] += 1
            diff[end + 1] -= 1
        times = sorted(diff.keys())

        n = len(persons)
        ans = [0] * n
        i = sum = 0
        for p, id in sorted(zip(persons, range(n))):
            while i < len(times) and times[i] <= p:
                sum += diff[times[i]]  # 累加变化量
                i += 1
            ans[id] = sum
        return ans

python3 解法, 执行用时: 4112 ms, 内存消耗: 179.9 MB, 提交时间: 2023-06-13 14:20:17

# 树状数组
class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], persons: List[int]) -> List[int]:
        res = [0] * len(persons)
        bit = BIT(int(1e9 + 10))
        for l, r in flowers:
            bit.add(l, r, 1)
        for i, p in enumerate(persons):
            res[i] = bit.query(p, p)
        return res


class BIT:
    def __init__(self, n: int):
        self.size = n
        self._tree1 = defaultdict(int)
        self._tree2 = defaultdict(int)

    @staticmethod
    def _lowbit(index: int) -> int:
        return index & -index

    def add(self, left: int, right: int, delta: int) -> None:
        self._add(left, delta)
        self._add(right + 1, -delta)

    def query(self, left: int, right: int) -> int:
        return self._query(right) - self._query(left - 1)

    def _add(self, index: int, delta: int) -> None:
        if index <= 0:
            raise ValueError('index 必须是正整数')

        rawIndex = index
        while index <= self.size:
            self._tree1[index] += delta
            self._tree2[index] += (rawIndex - 1) * delta
            index += self._lowbit(index)

    def _query(self, index: int) -> int:
        if index > self.size:
            index = self.size

        rawIndex = index
        res = 0
        while index > 0:
            res += rawIndex * self._tree1[index] - self._tree2[index]
            index -= self._lowbit(index)
        return res

python3 解法, 执行用时: 232 ms, 内存消耗: 39.3 MB, 提交时间: 2023-06-13 14:19:34

# 离散查询 + 最小堆
class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], persons: List[int]) -> List[int]:
        queries = sorted([(person, index) for index, person in enumerate(persons)])
        flowers = sorted(flowers)

        fi, res = 0, [0] * len(queries)
        pq = []
        for qi in range(len(queries)):
            while fi < len(flowers) and flowers[fi][0] <= queries[qi][0]:
                heappush(pq, flowers[fi][1])
                fi += 1
            while pq and pq[0] < queries[qi][0]:
                heappop(pq)
            res[queries[qi][1]] = len(pq)
        return res

python3 解法, 执行用时: 196 ms, 内存消耗: 38.7 MB, 提交时间: 2023-06-13 14:18:41

# 离散化 + 差分
class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], persons: List[int]) -> List[int]:
        diff = defaultdict(int)
        for left, right in flowers:
            diff[left] += 1
            diff[right + 1] -= 1

        # 离散化的keys、原数组前缀和
        keys = sorted(diff)
        preSum = [0] + list(accumulate(diff[key] for key in keys))
        return [preSum[bisect_right(keys, p)] for p in persons]

cpp 解法, 执行用时: 240 ms, 内存消耗: 75.7 MB, 提交时间: 2023-06-13 14:17:54

int op[50004],cl[50004];
class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
        int n=flowers.size();
        vector<int> ret(persons);
        for(int i=0;i<n;++i)op[i]=flowers[i][0],cl[i]=flowers[i][1];
        sort(op,op+n),sort(cl,cl+n);
        for(int&t:ret){
            int o=upper_bound(op,op+n,t)-op;
            int e=upper_bound(cl,cl+n,t-1)-cl;
            t=o-e;
        }
        return ret;
    }
};

上一题

下一题

详情