arrays - O(n) 线性搜索数组以查找最常见的项目

Question

我正在尝试为 O(n) 算法编写伪代码，该算法在排序数组中搜索最常出现的元素。

对数据结构和算法非常陌生，我已经有大约 2 年半没有编码了。我已经围绕这个主题做了一些阅读，我相信我正在掌握这些概念，但我正在努力解决上述问题。

这就是我到目前为止所拥有的一切，如果没有第二个“for”循环，我正在努力获得所需的结果，这使得算法成为 O(n^2) 我相信但我不确定我将如何处理具有不止一种频繁出现的元素。

如能提供任何帮助或指导，我将不胜感激。

 A=[i];
 Elem=0; 
 Count=0;
 For (i=0; j< A[n-1]; j++);
      tempElem=A[j];
      empCount=0;
      for(p=0; p<A[n-1; p++])   
          If(A[p]==tempElem)
             tempCount++:
      if(tempCount>Count);
        Elem==tempElem:
        Count=tempCount;
 Print(“The most frequent element of array A is”: Elem “as it appears” Count “times”)

Answer 1

内部循环不是你的 friend 。 :-)

你的循环体应该只关注两个逻辑位:

1. 这个元素和之前的元素一样吗？

   如果是，则增加当前项目的计数 (curr_count) 并转到下一个元素。

2. 否则，检查 curr_count 与迄今为止最好的。如果更好，则制作之前的元素并统计新的“最佳”数据。

   无论哪种方式，将计数设置回 1 并转到下一个元素。