給定整數陣列的常用3和正整數米，你的任務是找到的長度每個連續子陣列內的最常見的元件的頻率米在ARR。
回傳子陣列元素中這些最高頻率的陣列，按其相應子陣列的起始索引排序。您可以查看示例部分以更好地理解。
例子
對于arr = [1, 2] 和m = 2，輸出應為
occurrencesInSubarrays( arr , m ) = [1]。
?
示例 1
?
arr僅包含一個長度為m = 2 - arr [0..1] = [1, 2] 的連續子陣列。該子陣列包含 2 個最頻繁的元素 - 1 和 2，兩者的頻率均為 1。
因此，答案是 [1]。對于arr = [1, 3, 2, 2, 3] 和m = 4，輸出應該是
occurrencesInSubarrays( arr , m ) = [2, 2]。例子2
arr包含兩個長度為m = 4 的連續子陣列：
arr [0..3] = [1, 3, 2, 2] 只包含一個最頻繁的元素 - 2，其頻率為 2。
arr [1..4] = [3, 2, 2, 3] 包含兩個最頻繁的元素 - 2 和 3，它們的頻率都是 2。
將兩個子陣列的答案放在一起，我們得到陣列 [2, 2]對于arr = [2, 1, 2, 3, 3, 2, 2, 2, 2, 1] 和m = 3，輸出應該是
occurrencesInSubarrays( arr , m ) = [2, 1, 2, 2, 2 , 3, 3, 2]。例3
arr包含 8 個長度為m = 3 的連續子陣列：
arr [0..2] = [2, 1, 2] 只包含一個最頻繁的元素 - 2，它的頻率為 2。
arr [1..3] = [1, 2, 3] 包含三個最頻繁的元素- 1, 2, 3。
?它們都有頻率1.
arr [2..4] = [2, 3, 3] 只包含一個最頻繁的元素- 3，它的頻率是2.
arr [3.. 5] = [3, 3, 2] 只包含一個最頻繁的元素 - 3，其頻率為 2。
arr [4..6] = [3, 2, 2] 只包含一個最頻繁的元素 - 2，并且它的頻率是 2.
arr [5..7] = [2, 2, 2] 只包含一個最頻繁的元素 - 2，它的頻率是 3.
arr [6..8] = [2, 2, 2]只包含一個最頻繁的元素 - 2，它的頻率是 3。
arr[7..9] = [2, 2, 1] 只包含一個最頻繁的元素 - 1，其頻率為 2。將兩個子陣列的答案放在一起，我們得到陣列 [2, 1, 2, 2, 2, 3, 3, 2]。
我的方法是使用兩個 Hashmap。一個作為每一行的佇列，一個保存每行的總和。但它仍然是馬車。任何人都可以有任何想法來解決這個問題嗎？
uj5u.com熱心網友回復：
使用兩個映射：elt_to_frequency、frequency_to_count。前者跟蹤滑動視窗中每個元素的頻率，后者跟蹤每個頻率的計數。
每次滑動視窗移動時都以明顯的方式更新兩者。
還要跟蹤 max_frequency。如果 elt_to_frequency 大于它，則將其增加到新的 max_frequency。另一方面，如果 frequency_to_count[max_frequency] 降為零，則新的 max_frequency 比舊的 max_frequency 小 1。
線性時間，線性空間。
紅寶石代碼
def f(arr, m)
# Initialize everything
elt_to_frequency = Hash.new {|h, elt| h[elt] = 0} #Rubyism: new elts default to zero
frequency_to_count = Hash.new {|h, freq| h[freq] = 0}
max_frequency = 0
i = j = -1 # left & right indices
ans = []
0.upto(m-1) do |j|
elt = arr[j]
add_elt(elt, elt_to_frequency, frequency_to_count)
max_frequency = [max_frequency, frequency_to_count[elt]].max
end
ans << max_frequency
# Now slide the window & make updates. The window is [i, j] inclusive
m.upto(arr.size - 1) do |j|
i = j - m 1
new_elt = arr[j]
old_elt = arr[i-1]
add_elt(new_elt, elt_to_frequency, frequency_to_count)
subtract_elt(old_elt, elt_to_frequency, frequency_to_count)
if elt_to_frequency[new_elt] > max_frequency
max_frequency = elt_to_frequency[new_elt]
elsif frequency_to_count[max_frequency] == 0
max_frequency -= 1
end
ans << max_frequency
end
return ans
end
def add_elt(elt, elt_to_frequency, frequency_to_count)
elt_to_frequency[elt] = 1
new_freq = elt_to_frequency[elt]
frequency_to_count[new_freq] = 1
frequency_to_count[new_freq - 1] -= 1 # We'll have a negative count for 0 but dont' care
end
def subtract_elt(elt, elt_to_frequency, frequency_to_count)
elt_to_frequency[elt] -= 1
new_freq = elt_to_frequency[elt]
frequency_to_count[new_freq] = 1
frequency_to_count[new_freq 1] -= 1
end
結果
f([2,1,2,3,3,2,2,2,2,1], 3)
=> [2, 1, 2, 2, 2, 3, 3, 2]
uj5u.com熱心網友回復：
您可以使用字典來跟蹤m添加元素的最后一個元素的頻率，同時減去m索引后面的元素。
def maxFreqs(arr,m):
freqs = dict.fromkeys(arr,0) # frequency counters for range
result = []
for i,n in enumerate(arr,1): # once through the list
freqs[n] = 1 # add to frequencies
if i>m: freqs[arr[i-m-1]] -= 1 # remove element going out
if i>=m: result.append(max(freqs.values())) # output max frequencies
return result
print(maxFreqs([2, 1, 2, 3, 3, 2, 2, 2, 2, 1], 3 ))
[2, 1, 2, 2, 2, 3, 3, 2]
時間復雜度：O(NxM)，空間：O(N)，其中N是串列的大小，M是子陣列視窗的長度
uj5u.com熱心網友回復：
方法一：
- 創建一個大小為 的視窗
m。 - 存盤視窗中所有元素的頻率。
- 找到最大頻率值。
- 向前移動視窗直到我們到達陣列的末尾。
時間復雜度：O(N 2 )
空間復雜度：O(N)
public static int[] occurrencesInSubarrays(int[] arr, int m) {
int n = arr.length;
int[] ans = new int[n - m 1];
int k = 0;
HashMap<Integer, Integer> freq = new HashMap<>();
// storing frequencies of each element
for (int i = 0; i < m; i )
freq.put(arr[i], freq.getOrDefault(arr[i], 0) 1);
for (int i = m; i < n; i ) {
// find maximum frequency(value) in the hashmap
for (int val : freq.values()) {
ans[i - m] = Math.max(ans[i - m], val);
}
// remove element outside of current window
freq.put(arr[i - m], freq.getOrDefault(arr[i - m], 0) - 1);
// add new number in the window
freq.put(arr[i], freq.getOrDefault(arr[i], 0) 1);
}
// again store frequency for last window
for (int val : freq.values()) {
ans[n - m] = Math.max(ans[n - m], val);
}
return ans;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/335897.html