第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號安全,請及時綁定郵箱和手機(jī)立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

應(yīng)用所有交替操作后計算計數(shù)器的值

應(yīng)用所有交替操作后計算計數(shù)器的值

慕的地6264312 2021-04-09 16:13:16
我正在嘗試Codility使用給定的解決方案來解決的問題。該問題在下面提供:You are given N counters, initially set to 0, and you have two possible operations on them:increase(X) ? counter X is increased by 1,max counter ? all counters are set to the maximum value of any counter.A non-empty array A of M integers is given. This array represents consecutive operations:if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),if A[K] = N + 1 then operation K is max counter.For example, given integer N = 5 and array A such that:A[0] = 3A[1] = 4A[2] = 4A[3] = 6A[4] = 1A[5] = 4A[6] = 4the values of the counters after each consecutive operation will be:(0, 0, 1, 0, 0)(0, 0, 1, 1, 0)(0, 0, 1, 2, 0)(2, 2, 2, 2, 2)(3, 2, 2, 2, 2)(3, 2, 2, 3, 2)(3, 2, 2, 4, 2)The goal is to calculate the value of every counter after all operations.Write a function:class Solution { public int[] solution(int N, int[] A); }that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.The sequence should be returned as:a structure Results (in C), ora vector of integers (in C++), ora record Results (in Pascal), oran array of integers (in any other programming language).For example, given:    A[0] = 3    A[1] = 4    A[2] = 4    A[3] = 6    A[4] = 1    A[5] = 4    A[6] = 4the function should return [3, 2, 2, 4, 2], as explained above.Assume that:N and M are integers within the range [1..100,000];each element of array A is an integer within the range [1..N + 1].Complexity:    expected worst-case time complexity is O(N+M);    expected worst-case space complexity is O(N) (not counting the storage required for input arguments).看來他們使用2個存儲來保存和更新最小值/最大值,并在算法中使用它們。顯然,有一種更直接的方法可以解決該問題。將值增加1或?qū)⑺兄刀荚O(shè)置為建議的最大值,我可以做到這一點(diǎn)。缺點(diǎn)將是降低性能并增加時間復(fù)雜度。但是,我想了解這里的情況。我花了很多時間在示例數(shù)組上進(jìn)行調(diào)試,但是該算法仍然沒有什么令人困惑的地方。任何人都可以理解并可以向我簡要說明嗎?
查看完整描述

1 回答

?
慕俠2389804

TA貢獻(xiàn)1719條經(jīng)驗(yàn) 獲得超6個贊

這很簡單,他們會延遲更新。您始終跟蹤具有最高值(currMax)的計數(shù)器的值。然后,當(dāng)您獲得將所有計數(shù)器增加到該maxValue的命令時,這太昂貴了,您只是保存了上一次必須將所有計數(shù)器增加到maxValue時的那個值是currMin。

那么,何時將計數(shù)器值更新為該值?您懶惰地執(zhí)行它,只是在收到命令更新該計數(shù)器(增加它)時才對其進(jìn)行更新。因此,當(dāng)您需要增加計數(shù)器時,可以將計數(shù)器更新為其舊值和currMin之間的最大值。如果這是自N + 1命令以來對該計數(shù)器的第一次更新,則它應(yīng)具有的正確值實(shí)際上是currMin,并且它將大于(或等于)其舊值。一個您更新它,您添加1。如果現(xiàn)在又發(fā)生了一次增量,則currMin實(shí)際上并不重要,因?yàn)閙ax將采用其舊值,直到發(fā)生另一個N + 1命令為止。

第二個原因是要說明在最后一個N + 1命令之后沒有獲得增加命令的計數(shù)器。

請注意,在一個計數(shù)器上進(jìn)行2次增值操作之間可以有任意數(shù)量的N + 1命令。仍然得出結(jié)論,它應(yīng)該具有的值是最后一個N + 1命令時的maxValue,這并不重要,我們之前沒有使用先前N + 1中的另一個maxValue對其進(jìn)行更新,僅在乎最新。


查看完整回答
反對 回復(fù) 2021-04-21
  • 1 回答
  • 0 關(guān)注
  • 169 瀏覽

添加回答

舉報

0/150
提交
取消
微信客服

購課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動學(xué)習(xí)伙伴

公眾號

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號