算法面试题记录

1，在无序数组中查找满足条件之和为target的两个数

从头开始扫描数组，将扫描过的元素加入hash_map，对于正在扫描的元素a[i]在哈希表中查找值为target-a[i]的元素，如果有就返回两个数，整个时间复杂度为O(n)。

2，反转一个语句

首先按每个字符翻转整个字符串，然后从头开始扫描，使用一个标记记录扫描过程中遇到的单词开头位置，遇到空格或者到达末尾，就翻转从标记位置开始的这个单词。直到结束，

3，一个数组先降序后升序，如何找到中间最小的那个元素

使用二分法，是二分查找的变形。二分查找是比较a[mid]和target，这个是比较a[mid]和其左右侧元素。

while( low <= high ) {

mid = (low + high)/2;

if(a[mid] <a[mid-1] && a[mid] <a[mid+1]) return mid;

if(a[mid] < a[mid-1]) {low = mid;}

else{high = mid;} //这个时候元素只剩下a[mid] > a[mid+1]这一种情况；

}

基础面试题

对于超大数据集的问题，上来就先看看hash+分治能不能行:

1. 选一个hash函数，能将数据集范围的整数分到若干个桶中，每个桶中落入的数的个数能够内存处理即可

2. 每个桶内进行操作

3，归并各个桶