知识点：
创建数组，首先需要指定数组的容量大小
数组可以实现简单的哈希表，把数组的下标设为哈希表的键值（Key），数组中每一个数字设为哈希表的值（Value）
动态数组，如STL中的vector。当数据的数目超过数组容量会进行扩容，新的容量都是前一次的两倍，把之前的数据复制到新的数组中，再把之前的内存释放。这样对时间性能有负面影响，因此使用动态数组要尽量减少改变数组容量大小
数组名其实是一个指针，指向数组的第一个元素
int data1[] = { 1, 2, 3, 4, 5 }; int *data2 = data1; cout << sizeof(data1) << endl << sizeof(data2) << endl;
输出：20 4
sizeof(data1)求整个数组大小，sizeof(data2)为指针大小
面试题3
从二维数组的右上角或者左下角向内逐渐收缩，注意接受参数是个指针，用数组表示的话只能用一维数组
自己的实现：
1 bool Find(int* matrix, int rows, int columns, int number) 2 { 3 if (matrix == NULL) 4 return false; 5 int row = 0; 6 int column = columns -1; 7 for (column; column > 0; column--) //排查第一行 8 { 9 if (matrix[column] == number) 10 return true; 11 if (matrix[column] < number) 12 break; 13 } 14 for (row; row < rows; row++) //确定行号后检查对应行的列 15 { 16 if (matrix[row * columns + column] == number) 17 return true; 18 if (matrix[row * columns + column] > number) 19 return false; 20 } 21 return false; 22 }
书中示例：
1 bool Find(int* matrix, int rows, int columns, int number) 2 { 3 bool found = false; 4 5 if(matrix != NULL && rows > 0 && columns > 0) 6 { 7 int row = 0; 8 int column = columns - 1; 9 while(row < rows && column >=0) 10 { 11 if(matrix[row * columns + column] == number) 12 { 13 found = true; 14 break; 15 } 16 else if(matrix[row * columns + column] > number) 17 -- column; 18 else 19 ++ row; 20 } 21 } 22 23 return found; 24 }
完整代码：
1 // FindInPartiallySortedMatrix.cpp : Defines the entry point for the console application. 2 // 3 4 // 《剑指Offer——名企面试官精讲典型编程题》代码 5 // 著作权所有者：何海涛 6 7 #include "stdafx.h" 8 9 // 二维数组matrix中，每一行都从左到右递增排序， 10 // 每一列都从上到下递增排序 11 bool Find(int* matrix, int rows, int columns, int number) 12 { 13 bool found = false; 14 15 if(matrix != NULL && rows > 0 && columns > 0) 16 { 17 int row = 0; 18 int column = columns - 1; 19 while(row < rows && column >=0) 20 { 21 if(matrix[row * columns + column] == number) 22 { 23 found = true; 24 break; 25 } 26 else if(matrix[row * columns + column] > number) 27 -- column; 28 else 29 ++ row; 30 } 31 } 32 33 return found; 34 } 35 36 // ====================测试代码==================== 37 void Test(char* testName, int* matrix, int rows, int columns, int number, bool expected) 38 { 39 if(testName != NULL) 40 printf("%s begins: ", testName); 41 42 bool result = Find(matrix, rows, columns, number); 43 if(result == expected) 44 printf("Passed. "); 45 else 46 printf("Failed. "); 47 } 48 49 // 1 2 8 9 50 // 2 4 9 12 51 // 4 7 10 13 52 // 6 8 11 15 53 // 要查找的数在数组中 54 void Test1() 55 { 56 int matrix[][4] = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}}; 57 Test("Test1", (int*)matrix, 4, 4, 7, true); 58 } 59 60 // 1 2 8 9 61 // 2 4 9 12 62 // 4 7 10 13 63 // 6 8 11 15 64 // 要查找的数不在数组中 65 void Test2() 66 { 67 int matrix[][4] = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}}; 68 Test("Test2", (int*)matrix, 4, 4, 5, false); 69 } 70 71 // 1 2 8 9 72 // 2 4 9 12 73 // 4 7 10 13 74 // 6 8 11 15 75 // 要查找的数是数组中最小的数字 76 void Test3() 77 { 78 int matrix[][4] = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}}; 79 Test("Test3", (int*)matrix, 4, 4, 1, true); 80 } 81 82 // 1 2 8 9 83 // 2 4 9 12 84 // 4 7 10 13 85 // 6 8 11 15 86 // 要查找的数是数组中最大的数字 87 void Test4() 88 { 89 int matrix[][4] = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}}; 90 Test("Test4", (int*)matrix, 4, 4, 15, true); 91 } 92 93 // 1 2 8 9 94 // 2 4 9 12 95 // 4 7 10 13 96 // 6 8 11 15 97 // 要查找的数比数组中最小的数字还小 98 void Test5() 99 { 100 int matrix[][4] = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}}; 101 Test("Test5", (int*)matrix, 4, 4, 0, false); 102 } 103 104 // 1 2 8 9 105 // 2 4 9 12 106 // 4 7 10 13 107 // 6 8 11 15 108 // 要查找的数比数组中最大的数字还大 109 void Test6() 110 { 111 int matrix[][4] = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}}; 112 Test("Test6", (int*)matrix, 4, 4, 16, false); 113 } 114 115 // 鲁棒性测试，输入空指针 116 void Test7() 117 { 118 Test("Test7", NULL, 0, 0, 16, false); 119 } 120 121 int _tmain(int argc, _TCHAR* argv[]) 122 { 123 Test1(); 124 Test2(); 125 Test3(); 126 Test4(); 127 Test5(); 128 Test6(); 129 Test7(); 130 131 return 0; 132 }