前言

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

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

應用場景

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

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

Leetcode題目實戰(zhàn)

題目描述

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

思路

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

代碼

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實現(xiàn)差分數(shù)組的示例詳解的文章就介紹到這了,更多相關Java差分數(shù)組內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論