算法-数组(二)

数组系列的第二篇文章。

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

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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 212,294评论 6 493
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,493评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,790评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,595评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,718评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,906评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,053评论 3 410
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,797评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,250评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,570评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,711评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,388评论 4 332
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,018评论 3 316
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,796评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,023评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,461评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,595评论 2 350

推荐阅读更多精彩内容

  • 1.把二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不...
    曲终人散Li阅读 3,301评论 0 19
  • 说明: 本文中出现的所有算法题皆来自牛客网-剑指Offer在线编程题,在此只是作为转载和记录,用于本人学习使用,不...
    秋意思寒阅读 1,148评论 1 1
  • 1、用C语言实现一个revert函数,它的功能是将输入的字符串在原串上倒序后返回。 2、用C语言实现函数void ...
    希崽家的小哲阅读 6,253评论 0 12
  • 01 大概是王者玩多了(把锅推给王者),近来戾气很重,整个人变得激进,口不择言。比如我只是想表达我很激动,却不料脱...
    potatohorse阅读 9,557评论 1 6
  • 我不想去讨厌别人,也不想去在乎别人,更不想去抱怨谁,最后发现那样受伤的是自己,我发现做事,或者说做眼前的事能让人充...
    下雨了收衣服阅读 190评论 0 1