算法-数组(二)

作者: zero_sr | 来源:发表于2016-08-17 16:58 被阅读156次

数组系列的第二篇文章。

  • 调整数组顺序,使奇数位于偶数前面
  • 顺时针打印矩阵
  • 查找数组中出现次数大于一半的数字

1.调整数组顺序,使奇数位于偶数前面

问题描述:输入一个整数上数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,偶数位于后半部分。

算法思想

思路一:遍历数组,每遇到一个偶数,就将这个数字后面的所有数字向前移动一位,然后把这个数字放到数组末尾,这样每遇到一个偶数,就需要进行O(n)次移动,所以整个算法的时间复杂度为O(n^2).

思路二:既然是把数组中的技术和偶数分开,奇数在前,偶数在后,我们可以尝试使用两个指针,第一个指针指向开头,第二个指针指向结尾,
1.判断前一个指针指向的是否是奇数 ,如果是,则指针后移,直到遇到下一个偶数为止,否则和后一个指针(指向奇数)交换元素位置;
2.判断后一个指针指向的是否是奇数,如果是奇数,就和前一个指针指向的偶数交换位置,否则就指针前移,直到遇到下一个奇数。

调整数组{1,2,3,4,5}顺序的过程

代码

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

相关文章

  • 整数二分查找原理及代码模板

    1.整数二分算法原理 ps:数组具有单调性,则一定可以使用整数二分算法;但是,能够使用整数二分算法的数组,数组未必...

  • 算法-数组(二)

    数组系列的第二篇文章。 调整数组顺序,使奇数位于偶数前面 顺时针打印矩阵 查找数组中出现次数大于一半的数字 1.调...

  • 算法:数组(二)

    283. 移动零 - 力扣(LeetCode) (leetcode-cn.com)[https://leetcod...

  • java学习第九章(数组)

    数组 数组的循环 数字12345倒序打印 二维数组 二维数组的循环 数组找到最大值 数组的排序(冒泡算法) 变量交...

  • 数组

    一维数组的创建及使用二维数组的创建及使用数组的基本操作数组排序算法

  • Search Insert Position

    标签: C++ 算法 LeetCode 数组 二分查找 每日算法——leetcode系列 问题 SeSearch...

  • Search for a Range

    标签: C++ 算法 LeetCode 数组 二分查找 每日算法——leetcode系列 问题 Search f...

  • 分治算法

    分治算法 1. 随机产生一个整型数组,数组元素取值范围为两位正整数10-99; 2. 采用二分归并排序算法将该数组...

  • 二分查找算法

    二分查找算法或者折半查找算法,是一种在有序数组中查找某一特定元素的搜索算法。 搜索过程从数组的中间元素开始,如果中...

  • Search in Rotated Sorted Array

    标签: C++ 算法 LeetCode 数组 困难 二分法 每日算法——leetcode系列 问题 Search...

网友评论

    本文标题:算法-数组(二)

    本文链接:https://www.haomeiwen.com/subject/nimusttx.html