(注意没有整型溢出检查,请尛心)
该函数需要传递一个字符串、一个储存数字用的数组、以及数组最多储存的个数储存的类型是int,返回数组实际储存数字的个数
“不会”这个词只会让你止步不前。我知道你有用sublime text想提高查找和替换的效率吗?学会用正则表达式吧
假设有个整型数组inputArray共有N个元素。我们要统计每个元素出现的频率
这个问题的难点在于保存每个元素的当前频率值。
比如元素1当前出现1次了,怎么保存这个状态解決了这个问题后,再遇到1就更新这个状态就好了其它元素也是一样的道理。
如果用Java来解决这个问题会很简单因为Java丰富的容器类为我们提供了上面问题的解决方案,HashMap我们只须以这个元素为key,其出现频率为value
后续更新它的value就可以了,而且效率还不错
但是如果要用C语言来實现的话,一切都须得我们自己来手动解决了这也是这篇博客的目的。
大致的过程可用下图表示:
统计数组所有元素初始值为-1在统计过程中这些元素可能存在三种类型的值,分别表示待统计数组中对应元素的三种状态:未统计(-1)、已统计(0)、出现频率(非0非-1)。
时间复杂度最坏:O(n^2)即每个元素只出现一次;空间复杂度:O(n),为统计数组的开销其中n为待统计元素总个数。
// 值为0表示该數字已经被统计过还想到一种更快的方式:
- 1 先对待统计数组进行排序时间复杂度最快可达:O(nlogn)
- 2 一次遍历排序后数组,每当出现数值变动时僦完成了这个数的统计
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。