[剑指Offer笔记]3_数组

[剑指Offer笔记]3_数组

数组,字符串:连续空间

链表,树:大量指针操作

栈:与递归相关

队列:广度优先算法相关

数组

• O(1)时间读写元素;

• 可以用数组实现 哈希表 ;

  有了哈希表可以实现O(1)查找!

• 固定大小的数组,效率不高. STL 中的 vector

  先开辟一个小的空间,当空间不够时再分配更大的空间.每次为之前的2倍.

  使用动态数组要尽量计算减少改变容量大小的次数

• 注意:

  数组与指针的关系

面试题:

• 在一个二维数组中,每一行都按照从左往右递归的顺序排序,每一列都按照从上到下递增的书序排序.完成一个函数,输入一个这样的二维数组和一个数,判断该数是否在数组中.

分析:

• 取数组的右上角 arr[i][j] ,判断它和目标数字 target 的关系
• 若相等,则找到,若 arr target,则target不在这一列
• 注意边界的判断,防止越界.

代码实现:

class Solution {public:bool Find(int target, vector > array) {int rows &＃61; array.size();int cols &＃61; array[0].size();bool FOUND &＃61; false;int i &＃61; 0, j &＃61; cols - 1; // 左上角(i,j),i行j列while (1) {// 没有越界if (i >&＃61; 0 && i &＃61; 0 && j targetj--;}}else {break;}}return FOUND;}};