algorithm - 检查是否存在任何数字至少出现 array.size()/4 次

Question

给定一个未排序的数组，但相同的元素彼此相邻。可以检查数组是否包含至少出现 array.size()/4 次的任何元素？

使用哈希表进行线性扫描是微不足道的，我想知道是否有任何算法的复杂性更好。

谢谢。

标签： algorithmbinary-search

Answer 1

如果相同的元素总是彼此相邻只是为了遍历并找到具有最大条目数的元素。如果最大值 < array.size()/4 则没有元素满足您的条件。请参见下面带有 2 个 while 循环的示例 java 代码

int index=0, currentSize, maxSize = 0, currentElem;
while (index<array.length){
  currentElem = array[index];
  currentSize = 1;
  index++;
  while (index<array.length && currentElem==array[index]){
   currentSize++;
   index++;
  }

  if (maxSize<currentSize) {
    maxSize = currentSize;
  }
}

if (maxSize>=array.length/4) return "Yes";
else return "No";