Posted on by

Leader – Dominator解題紀錄

題目內容

題目頁面: https://app.codility.com/programmers/lessons/8-leader/dominator/

Leader概念教學

在LeetCode中，”Leader”通常指的是一個數組中出現次數超過數組長度一半的元素。因為這種元素在數組中出現的次數比其他元素都多，所以被稱為”Leader”。

LeetCode中的一些問題會要求你尋找數組中的Leader或者判斷數組中是否存在Leader。解決這些問題的一種常見方法是使用摩爾投票算法（Moore Voting Algorithm）。

摩爾投票算法的基本思想是遍歷數組，對於當前遍歷到的元素，如果它和當前候選元素相同，則將計數器加一，否則將計數器減一。當計數器為零時，更換當前的候選元素。最後剩下的候選元素就是可能的Leader，需要再次遍歷數組來驗證它是否真的是Leader。

需要注意的是，摩爾投票算法的前提是數組中一定存在Leader，如果數組中不存在Leader，那麼算法得出的結果可能是錯誤的。

摩爾投票算法

摩爾投票算法是一種快速尋找數組中出現次數超過一半的元素的方法，其基本思想已經在之前的回答中進行了介紹。這裡再介紹一下摩爾投票算法的實現方法。

假設我們要在數組中尋找出現次數超過一半的元素，可以使用一個計數器count和一個候選元素candidate來輔助實現。初始時，將count和candidate分別設為0和null。

遍歷數組，對於每一個元素：

  1. 如果count為0，將candidate設置為當前元素；
  2. 如果當前元素和candidate相同，將count加1；
  3. 如果當前元素和candidate不同，將count減1；
  4. 遍歷結束後，candidate就是可能的超過一半的元素，但需要再次遍歷數組來驗證它是否真的出現次數超過一半。

它的時間複雜度是O(n)

解題紀錄

function solution(A) {
    var candidate = 0
    var count = 0
    for(var i=0;i<A.length;i++){
        if(count == 0){
            candidate = A[i]
            count++
        }else if(candidate == A[i]){
            count++
        }else {
            count--
        }
    }
    var idx = []
    for(var i=0;i<A.length;i++){
        if(A[i] == candidate){
            idx.push(i)
        }
    }
    //console.log(idx)
    return idx.length > A.length/2 ? idx[0]:-1
}

https://app.codility.com/demo/results/trainingNPG8GS-3QA/

EquiLeader題目內容

題目連結: https://app.codility.com/programmers/lessons/8-leader/equi_leader/

解題想法

  1. 找出過半的那個數字
  2. 使用前綴和的方式去計算從0到現在的Leader的加總
  3. 計算在某個點的前面、後面是否有占全部長度的一半

我的解題

function solution(A) {
    var candidate = 0
    var count = 0
    for(var i=0;i<A.length;i++){
        if(count == 0){
            candidate = A[i]
            count++
        }else if(candidate == A[i]){
            count++
        }else {
            count--
        }
    }
    var amount_list = []
    var currentCount = 0
    for(var i=0;i<A.length;i++){
        if(A[i] == candidate){
            currentCount++
        }
        amount_list.push(currentCount)
    }
    var equi_leaders = 0
    for(var i=0;i<amount_list.length;i++){
        if(amount_list[amount_list.length-1]-amount_list[i] > (amount_list.length-i-1)/2 && amount_list[i] > (i+1)/2){
            equi_leaders++
        }
    }
    return equi_leaders
}