数组系列的第二篇文章。
- 调整数组顺序,使奇数位于偶数前面
- 顺时针打印矩阵
- 查找数组中出现次数大于一半的数字
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个指针来分开元素,这一系列的题都可以这样解决,关键只是修改判断条件。在顺时针打印矩阵中,主要把打印矩阵这一模型简化为一个一个圈,然后分析打印每一圈的步骤,确定边界条件。在查找数组中出现次数大于一半的数字中,主要是分析这一数组的特点,要找的这个数字出现的次数一定大于其他数字出现次数之和,利用好这个特点,代码就简单多了。好了,这次就到这里了,不足之处,欢迎指教~