的区域没有得到充分利用。
由于数组中的内存是连续的,于是可以根据下标在O(1)时间读/
写任何元素,因此它的时间效率是很高的。我们可以根据数组时间效率
高的优点,用数组来实现简单的哈希表:把数组的下标设为哈希表的键
值(Key),而把数组中的每一个数字设为哈希表的值(Value),这样
每一个下标及数组中该下标对应的数字就组成了一个键值-值的配对。
有了这样的哈希表,我们就可以在O(1)实现查找,从而可以快速高
效地解决很多问题。面试题35“第一个只出现一次的字母”就是一个很好
的例子。
为了解决数组空间效率不高的问题,人们又设计实现了多种动态数
组,比如C++的STL中的vector。为了避免浪费,我们先为数组开辟较小
的空间,然后往数组中添加数据。当数据的数目超过数组的容量时,我
们再重新分配一块更大的空间(STL的vector每次扩充容量时,新的容
量都是前一次的两倍),把之前的数据复制到新的数组中,再把之前的
内存释放,这样就能减少内存的浪费。但我们也注意到每一次扩充数组
容量时都有大量的额外操作,这对时间性能有负面影响,因此使用动态
数组时要尽量减少改变数组容量大小的次数。
在C/C++中,数组和指针是相互关联又有区别的两个概念。当我们
声明一个数组时,其数组的名字也是一个指针,该指针指向数组的第一
个元素。我们可以用一个指针来访问数组。但值得注意的是,C/C++没
有记录数组的大小,因此用指针访问数组中的元素时,程序员要确保没
有超出数组的边界。下面通过一个例子来了解数组和指针的区别。运行
下面的代码,请问输出是什么?
2021-10-19 15:52:38
7.15MB
offer
1