数组系列的第二篇文章。
- 调整数组顺序，使奇数位于偶数前面
- 顺时针打印矩阵
- 查找数组中出现次数大于一半的数字
1.调整数组顺序，使奇数位于偶数前面
问题描述：输入一个整数上数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，偶数位于后半部分。
算法思想
思路一：遍历数组，每遇到一个偶数，就将这个数字后面的所有数字向前移动一位，然后把这个数字放到数组末尾，这样每遇到一个偶数，就需要进行O(n)次移动，所以整个算法的时间复杂度为O(n^2).
思路二：既然是把数组中的技术和偶数分开，奇数在前，偶数在后，我们可以尝试使用两个指针，第一个指针指向开头，第二个指针指向结尾，
1.判断前一个指针指向的是否是奇数 ，如果是，则指针后移，直到遇到下一个偶数为止，否则和后一个指针(指向奇数)交换元素位置；
2.判断后一个指针指向的是否是奇数，如果是奇数，就和前一个指针指向的偶数交换位置，否则就指针前移，直到遇到下一个奇数。
代码
注意：代码中需要注意的地方是，在移动指针时，一直对pBegin,pEnd大小的判断，一旦pEnd>=pBegin，就可以结束循环了。
void ReorderOddEven0 (int *pData, unsigned int length)
{
if (pData == NULL || length == 0)
return;
int *pBegin = pData;
int *pEnd = pData + length - 1;//指向数组最后一个元素
while (pBegin < pEnd)
{
//如果前一个指针指向的是奇数，就一直往后移
while (pBegin < pEnd && (*pBegin % 2) == 1)
pBegin++;
//向前移动指针，直到指向奇数
while (pBegin < pEnd && (*pEnd % 2) == 0)
pEnd--;
if (pBegin < pEnd)
{
int temp = *pBegin;
*pBegin = *pEnd;
*pEnd = temp;
}
}
}
这样一道题解决了，那如果遇到要分离正数和负数的题呢？要将能被3整除的数排在数组前面，不能被3整除的排后面呢？是不是修改内层的两个while循环的条件就可以了。其实还有更好的办法。
思路三：将思路二的代码拆分开，用于解决这类的一系列问题，比如说将负数移动前面，将能被3整除的移到前面等。这些问题的解决方法没有多大的差异，唯一的差异就是在移动指针时的判断，我们可以使用一个函数，用于判断指针知否该移动，而原来的函数就负责移动指针。
代码
思路二的改进，更具可扩展性。
在下面的代码中，将判断是否移动指针的代码封装成一个函数，作为参数传入，降低和代码的耦合性，现在，这一类问题，我们都只需修改func函数就可以了。
//将移动指针和判断是否该移动分开
void Reorder(int *pData, unsigned int length, bool (*func) (int))
{
if (pData == NULL || length == 0)
return;
int *pBegin = pData;
int *pEnd = pData + length - 1;//指向数组最后一个元素
while (pBegin < pEnd)
{
//如果前一个指针指向的是奇数，就一直往后移
while (pBegin < pEnd && !func(*pBegin))
pBegin++;
//向前移动指针，直到指向奇数
while (pBegin < pEnd && func(*pEnd))
pEnd--;
if (pBegin < pEnd)
{
int temp = *pBegin;
*pBegin = *pEnd;
*pEnd = temp;
}
}
}
bool isEven(int num)
{
return (num % 2) == 0;
}
void ReorderOddEven1(int *pData, unsigned int length)
{
Reorder(pData, length, isEven);
}
2.顺时针打印矩阵
问题描述：输入一个矩阵，按照从外到内，顺时针顺序一次打印出每一个数字。
算法思想
这一题没有涉及到复杂的数据结构或者高级的算法，但是我们能想到代码应该会有很多循环，所以边界条件更为重要。既然是顺时针打印矩阵，我们可以把它想象成在矩阵上有若干个圈，每次用一个循环打印一圈之内的元素。现在我们考虑边界条件。
先看5*5的矩阵，最外层圈左上角的坐标是(0,0),下一层左上角的坐标是(1,1),最内层只有1个元素，左上角坐标为(2,2)。再看6*6的矩阵，最内层是4个元素，左上角的坐标也是(2,2)。假设每个圈的左上角是从坐(start,start)开始。
从以上分析，我们可以得到，6>start*2,5>start*2，也就是说最后一圈的左上角元素不能超过矩阵一半。这个就是我们得到的边界条件，没循环一次打印一圈元素。那么打印一圈元素的函数又要如何实现呢？
这里需要分几种情况，因为输入的矩阵不一定是行列相等的，所以打印最后一圈元素会有一下几种情况。打印4步的，打印3步的，打印2步的和打印1步的。
1.打印1步的：说明最后一圈只有一行元素，只用横向打印起始横坐标到终止点横坐标之间的元素就可以。
2.打印2步的，说明最后一圈只有一列，在第一次打印之后，需要纵向打印。前提条件就是终止行号大于起始行号。
3.打印3步的，说明至少有2行2列，也就是终止行号大于起始行号，且终止列号大于起始列号。
4.打印4步的，说明至少有3行2列，也就是终止行号至少要比起始行号大2，终止列号大于起始列号。
代码
下面是代码。在打印一圈时的几次判断比较容易出错，画个图分析一下就好了。
//打印一圈的元素,最多有4步
void PrintMatrixInCricule(int **numbers, int columns, int rows, int start)
{
int endX = columns - 1 - start;
int endY = rows - 1 - start;
//第一步，从左到右打印一行
for (int i = start; i <= endX; i++)
{
int number = numbers[start][i];
PrintNumber(number);
}
//第二步，从上到下打印一列
if (endY > start)
{
for (int i = start + 1; i <= endY; i++)
{
int number = numbers[i][endX];
PrintNumber(number);
}
}
//第三步，从右到左打印一行
if (endX > start && endY > start)
{
for (int i = endX - 1; i >= start; i--)
{
int number = numbers[endY][i];
PrintNumber(number);
}
}
//第四步，从下到上打印一列(2行3列)
if (endX > start && endY - 1 > start)
{
for (int i = enxY - 1; i > start; i--)
{
int number = numbers[i][start];
PrintNumber(number);
}
}
}
void PrintMatrix(int **numbers, int columns, int rows)
{
if (numbers == NULL || columns <= 0 || rows <= 0)
{
fprintf(stderr, "Invalid parameter！\n" );
exit(1);
}
int start = 0;
while (columns > start * 2 && rows > start * 2)
{
PrintMatrixInCricule(numbers, columns, rows, start);
start ++;
}
}
3.查找数组中出现次数大于一半的数字
问题描述：输入一个数组，这个数组中有一个数字的个数超过一半，查找这个数字。如{2,3,1,2,2,2,2,4,5},2有5个，超过了一半，就返回2。
算法思想
思路一：看到这个题，我们可能会想到，如果这个数组是排好序的就好了，和上次的“数字在排序数组中出现的次数” 的思路类似，我们可以在O(logn)时间内解决这个问题。
思路二：利用数组呃特点，在O(n)内找到这个数字。既然数组中存在一个数字出现的次数大于数组长度一半，那么可以确定这个数字出现的次数大于其他数字出现次数的总和。我们考虑在遍历数组的时候保存两个值，一个是数字，一个是数字出现的次数。当我们遍历到下一个元素时，如果这个数字和上一次保存的结果相同，次数+1；如果不同，次数-1，当次数减到0的时候，将保存的结果设置为当前的数字。由于我们要找的数字出现的次数总是最大的，所以最后一个把次数设置为1的数字就是我们要找的数字。遍历的时间复杂度为O(n).所以整个算法的时间复杂度也是O(n).
代码
基于思路二的代码，注意，我们不知道传入的的数组是否符合规格，有出现次数超过一半的数字，所以我们最后还需要验证一下。
int MoreThanHalfNum(int *numbers, int length)
{
if (numbers == NULL || length <= 0)
{
g_bInvalidInput = true;
fprintf(stderr, "Invalid parameter\n");
exit(1);
}
int result = numbers[0];
int times = 1;
for (int i = 1; i < length; i++)
{
if (times == 0)
{
result = numbers[i];
times = 1;
}
else if (result == numbers[i])
times ++;
else
times --;
}
if(!CheckMoreThanHalf(numbers, length, result))
return 0;
return result;
}
验证数组中是否存在出现次数超过一半的数字。
//检查数组中是否有超过一半的数字
bool CheckMoreThanHalf(int *number, int length, int result)
{
int time = 0;
for (int i = 0; i < length; i++)
{
if (numbers[i] == result)
time++;
}
bool isMoreThanHalf = true;
if (time * 2 < length)
{
g_bInvalidInput = true;
isMoreThanHalf = false;
}
return isMoreThanHalf;
}
总结
这次的3道题难度都不大，主要是分析问题，发现数组的特征。在调整数组顺序，使奇数位于偶数前面中，技巧在于使用2个指针来分开元素，这一系列的题都可以这样解决，关键只是修改判断条件。在顺时针打印矩阵中，主要把打印矩阵这一模型简化为一个一个圈，然后分析打印每一圈的步骤，确定边界条件。在查找数组中出现次数大于一半的数字中，主要是分析这一数组的特点，要找的这个数字出现的次数一定大于其他数字出现次数之和，利用好这个特点，代码就简单多了。好了，这次就到这里了，不足之处，欢迎指教~
