前言

昨天（2022-06-07）在做leetcode每日一題的時候，第一次看到了這個超級簡單但是很實用的算法---差分數組，差分數組是由原數組進化而來，值為原數組當前位置值減去上一個位置的值，看下面這個圖片就很清楚了。

從上圖中我們可以很清晰的看到，diffArray[1]=-3=srcArray[1]-srcArray[0]=-1-2，那么當我們在已知差分數組的情況下，如何推出原數組，同樣依據上面的關系，但是我們需要從index=0，依次將當前差分數組與原數組的上一個值進行累加。

應用場景

試想一個場景，我們需要將位置0～8的數值都加上一個相同的數值，如果在原數組上操作，我們需要更改9個位置的值，但是我們在差分數組的位置上操作，我們只需要更改兩個位置的值，即位置0和8分別加上值，我們通過差分數組就能得到位置0～8之間的其他位置的正確值。

這種方式在一次性更新大量數據時候性能提升更加明顯。

Leetcode題目實戰(zhàn)

題目描述

當 k 個日程安排有一些時間上的交叉時（例如 k 個日程安排都在同一時間內），就會產生 k 次預訂。給你一些日程安排 [start, end) ，請你在每個日程安排添加后，返回一個整數 k ，表示所有先前日程安排會產生的最大 k 次預訂。實現一個 MyCalendarThree 類來存放你的日程安排，你可以一直添加新的日程安排。MyCalendarThree() 初始化對象。int book(int start, int end) 返回一個整數 k ，表示日歷中存在的 k 次預訂的最大值。提示：0 <= start < end <= 10^9每個測試用例，調用 book 函數最多不超過 400次

思路

在上面的題目描述中，如果時間點有重合，這個時間點預定次數+1，最容易想到的就是暴力解法，每個時間點出現就將該時間點預定次數+1，但是看看數據量，最大值10^9，如果只有一個時間段[0-10^9]，那我們在時間和空間上都損失了不少。這時候我們就可以使用上面所說的差分數組，僅僅更新開始時間和結束時間，然后進行計算。我們可以使用一個map存儲差分數組更改的最終結果（差分數組開始時值全為0），key為開始時間或者結束時間點，value為預定次數，當出現一個日程[start,end)，我們需要將start位置預定次數+1，而因為是開區(qū)間，end并不包含在此次日程中，相當于在原數組中end-1位置的值+1，但是end位置的值沒變，所以差分數組中end位置的值需要-1。接下來看看具體實現代碼

代碼

TreeMap<Integer,?Integer>?treeMap;
? ?public?MyCalendarThree() {
? ? ? ?treeMap?=?new?TreeMap<>();
? }
public?int?book(int?start,?int?end) {
? ? ? ?if?(!treeMap.containsKey(start)) {
? ? ? ? ? ?treeMap.put(start,?0);
? ? ? }
? ? ? ?if?(!treeMap.containsKey(end)) {
? ? ? ? ? ?treeMap.put(end,?0);
? ? ? }
? ? ? ?treeMap.put(start,?treeMap.get(start)?+?1);
? ? ? ?treeMap.put(end,?treeMap.get(end)?-?1);
? ? ? ?//x1 - 0 = value1 x2 - x1 = value2
? ? ? ?int?answer?=?0;
? ? ? ?int?max?=?0;
? ? ? ?for?(Integer?value?:?treeMap.values()) {
? ? ? ? ? ?max?+=?value;
? ? ? ? ? ?answer?=?Math.max(max,?answer);
? ? ? }
? ? ? ?return?answer;
? }

到此這篇關于Java實現差分數組的示例詳解的文章就介紹到這了,更多相關Java差分數組內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論