给定一个数组返回其支配者发生的任何索引

Question

Dominator是一个在数组中超过一半位置的值.例如,在阵列中:[3,4,3,2,3,-1,3,3],值3出现在8个位置中的5个位置.5/8> 0.5,所以3是一个支配者:在这个数组中,支配者出现在索引上:0,2,4,6,7.如何编写给定数组的函数返回其支配者发生的任何索引.如果没有支配者,则该函数应返回-1.

试图用C解决它:

int arrdominator(int *A,int N)
{
    int i,j,idx=0,val=0,cnt=1;

    //I thought I would sort the array and then cound the dominating value instances,
    qsort(A,N,sizeof(A[0]),sort_fn_ascend);

    for(i=0;i<(N-1);i++)
    {
        for(j=i+1;j<N;j++)
        {
            if(A[i] == A[j])
            {
                cnt++;

                i++;
                break;
            }
        }
    }
}

但我无法找到在数组中找到支配者值然后返回其索引的解决方案.

Answer 1

我不打算解决这个给你,你要真这样做对你自己的,但这里有一些提示:

• 首先,既然你的规范说你必须返回一个索引数组(或-1),我建议你相应地更改你的函数的签名

• 第二,你应该将任务分成几部分.第一部分(排序后):确定相同数字的最长序列的长度(以及该序列的重复数).然后,测试序列是否长于N/2.如果是,请找出出现该数字的索引并返回此结果.由于您要通过排序来解决此问题,因此请确保保留原始数组的副本,因为您需要它来确定原始索引.

• 如果cnt要计算序列长度,则每次开始计算新序列时都必须将其重置为零.并且您将需要第二个变量maxSequenceLength来保持迄今为止发现的最长序列的长度,以及第三个变量valOfMaxSequence.

希望这可以帮助.