概念介紹
Counting Elements是一種計算數組中元素出現次數的概念。它通常用於解決一些與計數有關的問題，例如找出數組中出現次數超過一定閾值的元素，計算數組中不同元素的個數等。
在Counting Elements中，我們可以使用一個額外的數組counts，將數組中每個元素出現的次數記錄下來。counts[i]表示數組中元素i出現的次數，如果數組中不存在元素i，則counts[i]=0。
具體來說，Counting Elements算法的步驟如下：
- 創建一個長度為k的counts數組，其中k是數組中最大元素的值加1。
- 遍歷原始數組A，對於每個A[i]，增加counts[A[i]]的值。
- 計算任意元素的出現次數，只需要查詢counts數組中對應元素的值即可。
Counting Elements算法的時間複雜度為O(n)，其中n是數組的長度。它可以在線性時間內計算數組中元素的出現次數，因此非常適用於需要頻繁計算元素次數的問題。另外，Counting Elements算法還可以與其他算法結合使用，例如快速排序和二分查找等，以進一步優化計算效率。
使用時機
在許多與計數有關的問題中，Counting Elements是一種常見的解決方案。因此，在考慮使用Counting Elements時，可以考慮以下幾點：
- 問題是否需要計算元素出現的次數：如果問題需要計算數組中每個元素出現的次數，那麼Counting Elements可能是一個合適的解決方案。
- 數據集的大小：Counting Elements通常適用於數據集較小的情況下，因為需要額外的空間來存儲counts數組，並且在預處理階段中需要遍歷數組，這可能需要額外的時間和空間。
- 需要找出出現次數超過一定閾值的元素：如果需要找出數組中出現次數超過一定閾值的元素，例如Majority Element，那麼Counting Elements可能是一個合適的解決方案。
- 需要計算數組中不同元素的個數：如果需要計算數組中不同元素的個數，那麼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
我的作答
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
題目連結: MaxCounters – VIEW
我的解法
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))
