前言

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

從上圖中我們可以很清晰的看到，diffArray[1]=-3=srcArray[1]-srcArray[0]=-1-2，那么當(dāng)我們?cè)谝阎罘謹(jǐn)?shù)組的情況下，如何推出原數(shù)組，同樣依據(jù)上面的關(guān)系，但是我們需要從index=0，依次將當(dāng)前差分?jǐn)?shù)組與原數(shù)組的上一個(gè)值進(jìn)行累加。

應(yīng)用場(chǎng)景

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

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

Leetcode題目實(shí)戰(zhàn)

題目描述

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

思路

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

到此這篇關(guān)于Java實(shí)現(xiàn)差分?jǐn)?shù)組的示例詳解的文章就介紹到這了,更多相關(guān)Java差分?jǐn)?shù)組內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論