c - 给定一个数组，返回其支配符出现的任何索引

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。

希望这对您有所帮助。