Counting Elements

概念介紹

Counting Elements是一種計算數組中元素出現次數的概念。它通常用於解決一些與計數有關的問題,例如找出數組中出現次數超過一定閾值的元素,計算數組中不同元素的個數等。

在Counting Elements中,我們可以使用一個額外的數組counts,將數組中每個元素出現的次數記錄下來。counts[i]表示數組中元素i出現的次數,如果數組中不存在元素i,則counts[i]=0。

具體來說,Counting Elements算法的步驟如下:

  1. 創建一個長度為k的counts數組,其中k是數組中最大元素的值加1。
  2. 遍歷原始數組A,對於每個A[i],增加counts[A[i]]的值。
  3. 計算任意元素的出現次數,只需要查詢counts數組中對應元素的值即可。

Counting Elements算法的時間複雜度為O(n),其中n是數組的長度。它可以在線性時間內計算數組中元素的出現次數,因此非常適用於需要頻繁計算元素次數的問題。另外,Counting Elements算法還可以與其他算法結合使用,例如快速排序和二分查找等,以進一步優化計算效率。

使用時機


在許多與計數有關的問題中,Counting Elements是一種常見的解決方案。因此,在考慮使用Counting Elements時,可以考慮以下幾點:

  1. 問題是否需要計算元素出現的次數:如果問題需要計算數組中每個元素出現的次數,那麼Counting Elements可能是一個合適的解決方案。
  2. 數據集的大小:Counting Elements通常適用於數據集較小的情況下,因為需要額外的空間來存儲counts數組,並且在預處理階段中需要遍歷數組,這可能需要額外的時間和空間。
  3. 需要找出出現次數超過一定閾值的元素:如果需要找出數組中出現次數超過一定閾值的元素,例如Majority Element,那麼Counting Elements可能是一個合適的解決方案。
  4. 需要計算數組中不同元素的個數:如果需要計算數組中不同元素的個數,那麼Counting Elements也可能是一個合適的解決方案。

綜合以上幾點,可以初步判斷哪些問題可能需要使用Counting Elements。在實際應用中,還需要進一步評估和優化算法,以確保其效率和準確性。

練習題目1

題目連結: FrogRiverOne – VIEW

我的解法

function solution(X, A) {
    // Implement your solution here
    var filled = new Array(X).fill(false);
    var current_filled = 0;
    for (let index = 0; index < A.length; index++) {
        //console.log(filled)
        if(!filled[A[index]-1]){
            filled[A[index]-1] = true
            current_filled ++;
            if(current_filled == X){
                return index
            }
        }
    }
    
    return -1
}

測試通過,為100%!

練習題目2

題目連結: PermCheckVIEW

我的作答

function solution(A) {
    // Implement your solution here
    var arr = new Array(A.length).fill(0)
    for(var i=0;i<A.length;i++){
        arr[A[i]-1] = 1
    }
    return (arr.indexOf(0) == -1) ? 1 :0
}

練習題目3- MaxCounters

題目連結: MaxCountersVIEW

我的解法

function solution(N, A) {
    // Implement your solution here
    var arr = new Array(N).fill(0)
    var max_value = 0
    for(var i=0;i<A.length;i++){
        if(A[i]<=N){
            arr[A[i]-1]++
            if(max_value < arr[A[i]-1]){
                max_value = arr[A[i]-1]
            }
        }else{
            arr.fill(max_value)
        }
    }
    return arr
}

結果正確,但時間超時,只得到66的分數,代表需要再修改做法

我檢查了一下寫法,發現arr.fill(max_value)這行雖然只有一行,但是會是O(N)的複雜度,會增加許多的時間複雜度,因此,我嘗試最後再一次性的更新這個值,並且在每一步做加總時,檢查這個值是否需要被更新,就可以避免每次當A[i]>N時都得增加一次O(N)的時間複雜度。

https://app.codility.com/demo/results/training556V6C-HBV/

function solution(N, A) {
    // Implement your solution here
    var arr = new Array(N).fill(0)
    var max_value = 0
    var minimum_value = 0
    for(var i=0;i<A.length;i++){
        if(A[i]<=N){
            if(arr[A[i]-1] < minimum_value) arr[A[i]-1] = minimum_value
            arr[A[i]-1]++
            if(max_value < arr[A[i]-1]){
                max_value = arr[A[i]-1]
            }
        }else{
            //arr.fill(max_value)
            minimum_value = max_value
        }
    }
    
    for(var i=0;i<arr.length;i++){
        arr[i] = Math.max(arr[i], minimum_value)
    }
    return arr
}

練習題目4- MissingInteger

題目連結: MissingInteger: VIEW

這題的意思是說要找到A這個陣列裡面缺少的最小的正整數,所以我的解題思路就是先尋找陣列裡面的最大值,接下來設定一個陣列裡面預設值全部設為0,然後遍歷整個陣列把有出現過的index設定為1,接著再回傳該陣列最小值為1的index

function solution(A) {
    var max = Math.max(...A)
    if (max < 0){
        return 1
    }
    var sort = new Array(max).fill(0)
    // Implement your solution here
    for(var i=0;i<A.length;i++){
        if(sort[A[i]-1] == 0 && A[i] > 0){
            sort[A[i]-1] = 1
        }
    }
    for(var i=0;i<max;i++){
        if(sort[i-1] == 0){
            return i
        }
    }
    return max+1
}

結果如下,正確率為100%,複雜度為O(N)或O(N*log(N))


17年資歷女工程師,專精於動畫、影像辨識以及即時串流程式開發。經常組織活動,邀請優秀的女性分享她們的技術專長,並在眾多場合分享自己的技術知識,也活躍於非營利組織,辦理活動來支持特殊兒及其家庭。期待用技術改變世界。