时间戳

首页 > 解决方案 > 如何解决 Codility equiLeader 挑战

javascript - 如何解决 Codility equiLeader 挑战

问题描述

找到“领导者”后，我尝试在给定数组中找到可能的 equiLeaders 但找不到。试图找到其他人的解决方案，但无法理解他的所作所为。

我对我在他的代码中迷失的部分发表了评论。能得到它的人可以引导我完成那部分吗？尤其是那些计算

这是他的解决方案

function solution(A) {
    // I understand this part as he was trying to find the leader
    if (A.length === 1) return 0
    let maxRepetition = 1;
    let maxIndex = -1
    let occurance = new Object()
    for (let i = 0; i < A.length; i++) {
        if (occurance.hasOwnProperty(A[i])) {
            occurance[A[i]][0]++
            if (occurance[A[i]][0] > maxRepetition) {
                if (occurance[A[i]][0] > A.length / 2) {
                    maxRepetition = occurance[A[i]][0]
                    maxIndex = occurance[A[i]][1]
                }
            }
        }
        else {
            occurance[A[i]] = new Array()

            occurance[A[i]][0] = 1
            occurance[A[i]][1] = i
        }
    }

    leader = A[maxIndex]


    // THis is the part I am not getting where he was trying to get the possible equiLeaders

    let equiLeader = 0
    let stack = []
    let stackIndex = -1
    for (let i = 0; i < A.length; i++) {

        if (stack.length > (Math.floor(i / 2)) && (maxRepetition - stack.length > Math.floor((A.length - i) / 2))) {
            equiLeader++
        }
        if (A[i] === leader) stack.push(i)

    }


    return equiLeader

}

这是完整的问题

给定一个由 N 个整数组成的非空数组 A。

这个数组的前导是出现在 A 的一半以上元素中的值。

equi leader 是一个索引 S 使得 0 ≤ S < N - 1 和两个序列 A[0], A[1], ..., A[S] 和 A[S + 1], A[S + 2 ], ..., A[N − 1] 具有相同值的领导者。

例如，给定数组 A 满足： A[0] = 4 A[1] = 3 A[2] = 4 A[3] = 4 A[4] = 4 A[5] = 2

我们可以找到两个 equi 领导者：

    0, because sequences: (4) and (3, 4, 4, 4, 2) have the same leader, whose value is 4.
    2, because sequences: (4, 3, 4) and (4, 4, 2) have the same leader, whose value is 4.

目标是计算 equi 领导者的数量。

写一个函数：

function solution(A);

即，给定一个由 N 个整数组成的非空数组 A，返回 equi 领导者的数量。

例如，给定： A[0] = 4 A[1] = 3 A[2] = 4 A[3] = 4 A[4] = 4 A[5] = 2

如上所述，该函数应返回 2。

为以下假设编写一个有效的算法：

    N is an integer within the range [1..100,000];
    each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].

标签： javascriptalgorithm

解决方案

我找到了一个解决方案，它非常简单，如果我们可以找到任何元素的最大值，并且通过第二个循环将其分成两个就可以产生正确的结果。

这是使用Javascript的代码，请看。

function solution(A) {
// write your code in JavaScript (Node.js 8.9.4)
 let totalEleFound = {};
for(let i=0;i<A.length;i++){
    if(!totalEleFound[ A[i] ]){
        totalEleFound[ A[i] ] = 1;
    }
    else{
        totalEleFound[ A[i] ]++;
    }

}

//console.log("totalEleFound",totalEleFound);
let maxOccures = 0;
for(const [key,value] of Object.entries(totalEleFound) ){
    maxOccures = Math.max(maxOccures,Math.floor(value/2))
}

return maxOccures;
}

祝你编码愉快，干杯。

推荐阅读