[leetcode]3318. Find X-Sum of All K-Long Subarrays I

Benjamin
·
·
IPFS
輸入一個數字陣列nums以及數字k和x,以nums中每k個為一組(1~k, 2~k+1 ...)統計各數字的出現次數,依照次數由多到少,同次數由數字大到小排序,將前x個數字出現的總值相加,輸出一個由這些總值組成的陣列。

※:這題是leetcode週賽419th的題目

如題目範例,第一組測資

輸入:nums = [1,1,2,2,3,4,2,3], k = 6, x = 2

每6個為一組得到
[1,1,2,2,3,4]、[1,2,2,3,4,2]、[2,2,3,4,2,3]

出現次數多寡分別為(列出的順序即為前面說明的排序規則)
{1:2, 2:2, 3:1, 4:1}、{2:3, 4:1, 3:1, 1:1}、{2:3, 3:2, 4:1}

取得出現次數前2多的數字之總值相加
1x2+2x2、2x3+4x1、2x3+3x2 => [6, 10, 12]

[6, 10, 12]就是答案

題目:3318. Find X-Sum of All K-Long Subarrays I
關鍵字:演算法、有序集合(SortedSet)、有序映射表(SortedMap)


這題的重點是如何有效率的解決問題,理解題目之後可以非常直覺的依照題目要求寫出如下的程式(細節省略)。

public int[] findXSum(int[] nums, int k, int x) {
    int[] answer = new int[nums.length - k + 1];
    for(int index = 0; index < nums.length - k; index++) {
        int[] subArray = getSubArray(nums, index, k);
        // 計數、排序、加總
        answer[index] = ??? // 加總結果
    }
    return answer;
}

private int[] getSubArray(int[] nums, int fromIndex, int length) {
    // 取得目標子陣列
    // ...
}

這樣的寫法對我來說並不理想,所以並沒有嘗試能否通過leetcode的測試。不理想的原因是有多餘的計算,先統計1st~6th再統計2nd~7th的過程中,2nd~6th就被重複讀取了,具體的統計次數會是「(n - k + 1)*k」次。

我所期望的是只讀取nums每個數字一次,總共n次就得到最後答案的做法。


符合期望的理想解法

建立了一個類別XSumData,提供加入和移除數字的方法,並在這過程中更新該數字目前累積出現的次數。

XSumData的變數與函式

記錄次數的動作為了讀取的效率分成兩個物件,nowCountMap記錄每個數字目前出現的次數,dataMap記錄每個次數目前有哪些數字符合,並且使用有序的Map和Set,讓出現次數和數字都由大到小排列。

使用add加入新的數字時更新nowCountMap把新數字的出現次數+1,並取得這個計算後的值。
如果是1就表示原本沒有記錄,只要把這個數字增加到次數1的分組就行;2以上則要移出原本的組別加入新的分組,例如出現第3次時就不是出現2次的數字,而要加入3次的分組了。

使用remove將要排除的數字次數-1,也把所屬的分組-1。把要加入的要移除的都處理完之後再呼叫getSum取得符合的計算結果。


回到題目,題目要記錄的是每k個一組的結果,首先add前k個數字的次數,getSum取得1~k的答案,再把第1個數字remove並add第k+1個數字,再次使用getSum得到2~k+1的答案......直到結束,這過程中反覆透過getSum蒐集的數值列表就是答案。

這個做法的好處是nums的每個數字都只有取得1~2次,也不用重複計算和排序,而且很容易讀&說明。

執行結果

對於效率這次已經滿足,所以就不繼續研究其他寫法了。

CC BY-NC-ND 4.0 授权

喜欢我的作品吗?别忘了给予支持与赞赏,让我知道在创作的路上有你陪伴,一起延续这份热忱!