c++ - 给定一个范围，我必须计算数组中数字的频率。给定的解决方案是否有效？

Question

#include<iostream.h>

int main()
 {
   int a[10]={1,2,3,5,2,3,1,5,3,1};
   int i;
   int c[10]={0};

   for(i = 0 ; i < 10 ; i++)
       c[a[i]]++;

   for(i=0;i<10;i++)
      cout<<i<<": "<<c[i]<<endl;

   return 0;
 }

该算法的运行时间为 O(n)，但它占用了 O(n) 的额外空间。我可以做得更好吗？

谢谢!

Answer 1

取决于对您来说重要的是什么 - 您可以创建一个算法，时间复杂度为 O(n^2)，但空间复杂度为 O(1)(使用两个循环，请参见下面的代码)，但您无法提高下面的时间复杂度O(n).

for(i=0;i<10;i++) {
  count = 0;
  for(j=0;j<10;j++)
    if (c[j] == i) count++;
  cout<<i<<": "<<count<<endl;
}

O(1) 空间的另一种可能性是对数组进行就地排序，然后遍历一次，使用就地合并排序应该具有时间复杂度 O(n log n)。