查找列表中出现的最常见的10号数字

我如何在下面的序列中找到相同数字的最多出现次数？查找列表中出现的最常见的10号数字

1,5,4,3,2,5,3,1,5,3,7,5,7

这种情况下的答案是5。

我倾向于将每个数字添加到列表中，如果该数字已经在列表中，则增加一个计数器。在这种方法中，我想我需要为每个数字设置一个计数器。什么是一个人最容易理解的解决方案？

在这种情况下，我用java

这是不工作的尝试：

斯蒂芬的回答略有修改，但这个工程 -

public class Main { 

    public static void main(String args[]){ 

     int[] numbers = {1,5,4,3,2,5,3,1,5,3,7,5,7,7,7,7,7};   
     int[] counterArray = new int[numbers.length]; 

     for (int i = 0; i < numbers.length; ++i){ 
      counterArray[numbers[i]] = counterArray[numbers[i]] + 1; 
     } 

     int maxNumber = 0; 
     for (int i = 0; i < numbers.length; ++i){ 
      if(counterArray[i] > counterArray[maxNumber]) 
      { 
       maxNumber = i; 
      } 
     } 

     System.out.println(maxNumber); 
    } 

}

来源

2011-12-06 blue-sky

你在用什么语言？ – Cyclonecode

定义优雅，请？更小的空间？计算时间更少？较少的源代码？另外，你的数字可以被认为是小的？ – thiton

我使用java，但伪代码就足够了。通过优雅，我的意思是让人们了解步骤简单。 –

当您知道您的值将介于0和9之间时，这会给您O（n）处理时间，内存占用（不包括您已有的初始数组）为O（1），因此counterArray = new int[10];

int[] numbers = {1,5,4,3,2,5,3,1,5,3,7,5,7}; 
//int[] counterArray = new int[10]; // use this if the max value of the in the array 'numbers' is known to be 9 
int[] counterArray = new int[numbers.length]; // Use this if the max value of the array is not known. 
// or we can quickly iterate O(n) operation to find the max value and use that 

for (int i = 0; i < numbers.length; ++i){ 
    counterArray[numbers[i]] = counterArray[numbers[i]] + 1; 
} 

int maxNumber = 0; 
for (int i = 0; i < numbers.length; ++i){ 
    if(counterArray[i] > countarArray[maxNumber]) 
    { 
     maxNumber = i; 
    } 
} 

Console.WriteLine("Number: " + maxNumber.ToString() + " occurs " + countarArray[maxNumber].ToString() + " times.");

的另一种方式，以减少过度的内存使用情况将是找到最小和最大值用O（n）和然后创建该阵列，以适合数量的值（记住由min值来抵消阵列位置）。

来源

2011-12-06 11:15:00 Seph

算法一（具有O（n）时间复杂度和O（1）存储器复杂度）：

正如你所说，设置一个计数器数字（10个计数器）并扫描一次列表。 C代码：

//int the_given_array[n]; 

int counter[10]; 
int ix, result; 
memset(counter,0,10); 

for(ix=0; ix<n; ix++) counter[the_given_array[i]]++; 

result = 0; 
for(ix=1; ix<10; ix++) if(counter[ix]>counter[result]) result = ix;

算法的两个（具有O（N^2）时间复杂度和O（1）存储器的复杂性）：

注：这其中有没有优势比如果你是第处理base10数字（有限数字）！

设置当前目标编号的计数器，并扫描列表进行计数。然后计算另一个数字等等。保持相同数字的最多出现次数最多。你必须最多扫描列表n次。要获得更多速度，您可能需要使用GPU编程来并行处理每个数字。

来源

2011-12-06 09:00:23 Skyler

对于算法一，它几乎不是O（n）的内存复杂度，因为最多只能有10个项目在数组中，因为我们只处理base10数字{0,1,2,3,4,5,6， 7,8,9}'。 – Seph

@Seph那么它会是O（1）的内存复杂度。我误解了它仅仅意味着十进制符号。 – Skyler

既然你想要一个快速的算法，你提出的解决方案确实是最快的。初始化大小10的阵列为0，然后简单地说：

for (int i: arrayList) ++counterArray[i]

由于轻微的平均时优化，你可以只保留中最常见的两个数字的运行计数器，并停止如最常见的搜索不仅仅是第二位最常见的数字，还有待审查的数字在哪里。

来源

2011-12-06 09:04:15 Noxville

我错过了一些东西，你能看看我发布的问题代码吗？ –

查找列表中出现的最常见的10号数字

回答

相关问题