数组的相关算法要简单一些，之前写过的和现在遇到的整理了一下。
数组：数组是较为简单的数据结构，它占据一块连续的内存，并按照顺序存储数据。数组需要事先知道容量大小，然后根据大小分配存储空间，所以数组的空间利用率不高。数组有很好的查找效率，能在O(1)内找到元素。所以我们可以基于数组实现简单的hash表，提高查找效率。
数组和指针的关系：在C语言中，我们声明一个数组时，数组名也是一个指针，数组有大小的限制，但是指针没有限制，所以在使用指针访问数组时，要注意不能越界。对数组和指针求sizeof时，有以下需要注意的地方：
1.int data[] = {0,1,2,3,4};对data求sizeof是20，因为数组中有5个整数，每个整数占4个字节。
2.int *pData = data;对pData求sizeof是4，因为pData声明为一个指针，在32位系统中，对任意指针求sizeof结果都是4。
3.void fun(int data[]){...}；在函数中对data求sizeof时，结果是4，因为C语言中将数组作为参数传递时，会自动退化为指针，结果还是4.
概念就介绍这些，进入正题。
- 二维数组中的查找
- 旋转数组的最小数字
- 数字在排序数组中出现的次数
1.二维数字中的查找
问题描述：每行从左到右，每列从上到下递增的二维数组中，判断某个数是否存在。
递增的二维数组
算法思想
思路一：常规思路，我们很快就能想到遍历二维数组，和要查找的数字比较，判断是否存在。这样的方法时间复杂度为O(n^2)，效率很低。
思路二：我们可以利用递增的二维数组的特点，选定数组中的一个点，和要查找的key比较，如果key大于这个数，就在这个数的下面和右边查找，如果小于这个数，就在这个数的上面和左边查找，这个方法要比一个一个遍历好，但是存在一个问题，就是上面和右边方向上的查找会有重复的查找的地方。
思路三：在思路二上进行改进。我们之前的查找都是从左上角开始，那么从右上角开始呢？以上的矩阵，假如我们查找的是7，从右上角开始，先比较9和7，9比7大，9又是本列的第一个，那么可以确定，9所在的列数字都大于7，我们可以排除最后一列，前移一列。比较8和7，8大于7，同样的思想我们可以排除8所在的列。接下来比较2和7，2小于7，那么2所在的行前面的数字都小于7，可以不必再比较了，直接排除2所在的行。以此类推，我们很快就可以定位到7。
代码
思路清楚之后，代码就简单多了。
从矩阵的右上角开始进行判断，最快的排除不需要比较的列和行
1.当前元素>number,那么当前元素所在的行就可以排除-->缩小比较范围
2.当前元素<number，那么当前元素所在列可以排除
3.当前元素=number，返回true
注：传入二维数组的时候被强转成了指针，所以在取出二维数组中的数字时，要更具指针的操作规范来。
bool Find(int* matrix, int rows, int columns, int number)
{
bool found = false;
if (matrix != NULL && rows > 0 && columns > 0)
{
int row = 0;
int column = columns - 1;
while (row < rows && column >= 0)
{
if (matrix[row * columns + column] == number){//相当于matrix[row][column]
found = true;
break;
}
else if (matrix[row * columns + column] > number)
column--;
else
row++;
}
}
return found;
}
旋转数组的最小数字
问题描述：把数组开头的几个数字移动到数组的末尾，成为数组的旋转，输入一个递增数组的旋转，找到数组中最小的数字。
算法思想
思路一：一次遍历就可以找到最小的数字。时间复杂度为O(n).
思路二：利用递增数组的特点，利用二分法查找。我们可以发现递增数组旋转之后之后可以得到两个排序的子数组，且第一个数字会大于或者等于最后一个数字，两个排序子数组的分界点就是这个最小的数字，这样在一定程度上排序的数组，我们可以尝试使用二分法的思想。使用两个指针，一个指向数组头，一个指向数组尾，接下来可以找到中间元素，如果中间元素大于第一个元素，中间元素位于前面的子数组中，就把前一个指针移动到中间元素的位置；如果中间元素小于后一个指针指向的元素，说明中间元素位于后面的子数组中，就把后一个指针移到中间元素的位置，这样就减少了一半查找范围。当第一个指针和后一个指针相差1时，那么后一个指针所指就是最小元素了。时间复杂度为O(logn).
在数组{3，4，5，1，2}中找最小值
改进：以上思路还存在bug，我们开考虑这样的数组，如图，在第一个数组中，我们定位到中间元素后发现，前一个指针所指，中间元素和后一个指针所指都是一样，如果这个时候简单的把中间元素归到前一个子数组中，那么默认最小元素在中间元素的后面就出错了。原因在于这样的中间元素我们不能确定它是属于后面还是属于前面，这时只能顺序查找了。
数组{0，1，1，1，1}的旋转数组
代码
分析结束可以看代码了。
注意：在Min函数中，我们把indexMid初始化为index1，也就是指向第一个元素，当传入的数组是递增数组时（原数组本身也是数组的一个旋转数组），第一个元素就是最小的，这时函数会返回第一个元素。
//当index1,indexMid,index2所指元素都相等的时只能顺序查找
int MinInOrder(int *numbers, int index1, int index2)
{
for (int i = index1 + 1; i <= index2; i++)
{
if (result > numbers[i])
{
return numbers[i];
}
}
return numbers[index1];
}
//查找旋转数组中的最小数
int Min(int *numbers, int length)
{
if (numbers == NULL || length < 0)
{
fprintf(stderr, "Invalid parameter\n" );
exit(1);
}
int index1 = 0;
int index2 = length - 1;
int indexMid = index1;
while (numbers[index1] >= numbers[index2])
{
if ((index2 - index1) == 1)
{
indexMid = index2;
break;
}
indexMid = (index2 + index1) / 2;
//特殊情况，无法判断indexMid是属于哪一个子数组
if (numbers[index1] == numbers[indexMid] && numbers[indexMid] == numbers[index2])
return MinInOrder(numbers, index1, index2);
//中间元素属于前一个子数组
if (numbers[indexMid] > numbers[index1])
index1 = indexMid;
else if (numbers[indexMid] < numbers[index2])
index2 = indexMid;
}
return numbers[indexMid];
}
数字在排序数组中出现的次数
问题描述：统计一个数字在排序数组中出现的次数。如果数组{1,2,3,3,3,3,4,5}和数字3,3在数组中出现了4次，返回4.
这个可以看做是查找问题，关注排序数组几个字。
算法思想
思路一：最简单直接的思路就是一次遍历数组，进行统计，时间复杂度为O(n)。
思路二：常规的思路人人都能想到，虽然简单，但是考虑到数组的特点，注意，这里的数组是排序数组。说到排序数组，我们可以想到二分查找，那么如果把二分查找的思想迁移到这里呢？先找到最中间的元素，如果最中间的元素小于或者大于要统计次数的数字，那么范围减少一半，其实提高了效率，但是如果最中间的数组等于要查找的数字呢？我们就需要向两边查找，一直找到第一个数字和最后一个数字，数字在长度为n的数组中有可能出现n次，所以，时间复杂度为O(n),和思路一的时间复杂度相同了。
思路三：思路二的改进。假设要统计次数的数字为key,在思路二中，时间耗费主要是在确定第一个key和最后一个key的时候，那么如果用二分法获取第一个key和最后一个key的位置呢？先找到中间数字，如果比key小，说明第一个key在后半部分，如果比key大，说明第一个key在前半部分，如果相等的话，先看中间数字的前一个是不时也等于key，如果不等，就可以确定中间数字就是第一个key，如果相等，说明第一个key在前一半，继续查找，找最后一个key的方法也类似，可以用递归实现。这样的算法，找第一个key的时候时间复杂度为O(logn)，找最后一个key的时候，时间复杂度也是O(logn)，所以总的时间复杂度也是O(logn)。
代码
下面是思路三的代码，有以下需要注意的地方：
- 在FindFirstK和FindLastK函数中，在判断中间元素的前一个元素或后一个元素是否是key时，要先判断是否到达数组边界，防止越界。
- 在函数GetNumberOfK中，计算key出现的次数时先判断了firstIndex和lastIndex是否都大于-1，这是因为只要有一个值为-1，那么数组中就不可能存在这个key。因为在FindFirstK和FindLastK中，只有找不到key才会返回-1，既然数组中没有key，那么自然就不会执行middle==key下面的判断了，而这里，就是FindFirstK和FindLastK两个函数不同的地方。也就是说，当数组中没有key时，FindFirstK和FindLastK两个函数执行的过程都是一样的。所以，我们也可以改进下面的代码，在GetNumberOfK中，计算了firstIndex之后先判断其是否等于-1，如果等于-1就，不必再计算lastIndex了，直接返回0.
//递归确定第一个key的下标
int FindFirstK(int *data, int length, int start, int end, int key)
{
if (start > end)
return -1;
int middleIndex = (start + end) / 2;
int middle = data[middleIndex];
if (middle == key)
{
//先判断是否大于0，再计算data[middleIndex-1]防止越界
if ((middleIndex > 0 && data[middleIndex - 1] != key)
|| middleIndex == 0)
return middleIndex;
else
end = middleIndex - 1;
}
else if (middle < key)
start = middleIndex + 1;
else//middle > key
end = middleIndex - 1;
FindFirstK(data, length, start, end, key);
}
//递归确定最后一个key的位置
int FindLastK(int *data, int length, int start, int end, int key)
{
if (start > end)
return -1;
int middleIndex = (start + end) / 2;
int middle = data[middleIndex];
if (middle == key)
{
if ((middleIndex < length - 1 && data[middleIndex + 1] != key)
|| middleIndex == length - 1)
return middleIndex;
else
start = middleIndex + 1;
}
else if (middle < key)
start = middleIndex + 1;
else//middle > key
end = middleIndex - 1;
FindLastK(data, length, start, end, key);
}
int GetNumberOfK(int *data, int length, int key)
{
int count = 0;
if (data != NULL || length > 0)
{
int firstIndex = FindFirstK(data, length, 0, length - 1, key);
int lastIndex = FindLastK(data, length, 0, length - 1, key);
if (firstIndex > -1 && lastIndex > -1)
count = lastIndex - firstIndex + 1;
}
return count;
}
总结
这次的三道题说是数组相关的算法题，也可以说是和查找算法题，在二维数组中的查找中，我们利用了二维递增数组的规律，每次都找右上角的数组，便于快速排出行或者列；在旋转数组的最小数字和计算数字在排序数组中出现的次数中，我们利用了排序数组的特点，用二分法进行查找，其实是迁移了二分查找的思想，进行了变换得到的。
好了，这次就到这里了。不足之处，还请多指教。
网友评论