[算法]模式识别-Array、HashTable

Author Avatar
与狼同行 11月 22, 2016

Array

数组可以通过下标随机访问元素。所以在修改、读取某个元素的时候效率极高,具有O(1)的时间复杂度。在插入、删除的时候需要移动后面的元素,所以平均时间复杂度O(n)。通常,数组这个数据结构不是很适合增减元素。

HashTable

Hash Table几乎可以说是最重要的数据结构了。存储的基本元素是键值对。寻找、插入的时间复杂度都是O(1)。
C++提供了map容器,可以插入、删除、寻找键值对,底层以平和二叉树的方式实现,根据键值对排序。严格来说,map不是一个哈希表,原因是时间复杂度从O(1)编程O(log n),但是好处是能根据顺序地输出元素。
unorder_map更加符合传统哈希表的定义。它的时间复杂度为O(1)

技巧

1. 当遇到要统计元素一个元素的出现个数时,应该直觉的反应去使用哈希表。键是元素,值是出现的个数。
例如这个题目:
如何判断一个字符的字符是不是都是唯一的?

1
2
3
4
5
6
7
8
9
10
bool isUnique(string input){
bitset<256> hashMap;
for(int i=0;i<input.length();i++){
if (hashMap[(int)input[i]]) {
return false;
}
hashMap[(int)input[i]] = 1;
}
return true;
}

字符通常都是255个ASCII码,利用ASCII索引,比如a对应97。比map要节省内存空间。写之前可以和面试官进行交流确认。

2. 当遇到当前节点需要依赖部分之前的部分结果时,可以考虑使用哈希表来记录之前的结果。本质类似于动态规划,利用哈希O(1)的时间复杂度来利用之前的结果。
从一个数组中找出一对元素,其和是一个给定的目标数字,假设数组中只存在一个符合要求的数值对,返回这些数值的下标(例如(i,j),较小的下标在前面)

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> addsToTarget(vector<int> &numbers,int target) {
unordered_map<int, int> numberToIndex;
vector<int> vi(2);
for (auto it = numbers.begin(); it < numbers.end(); it++) {
if (numberToIndex.count(target-*it)) {
vi[0]=numberToIndex[target-*it]+1;
vi[1]=(int)(it-numbers.begin())+1;
return vi;
}
numberToIndex[*it]=(int)(it-numbers.begin());
}
return vi;
}