剑指Offer面试题:13.调整数组顺序使奇数位于偶数前面

一、题目:调整数组顺序使奇数位于偶数前面

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

  例如有以下一个整数数组:12345,经过调整后可以为:15342、13542、13524等等。

二、解题思路

2.1 基本解法

  如果不考虑时间复杂度,最简单的思路应该是从头扫描这个数组,每碰到一个偶数时,拿出这个数字,并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位,这时把该偶数放入这个空位。由于每碰到一个偶数就需要移动O(n)个数字,因此总的时间复杂度是O(n2)

2.2 高效解法

  这里可以参考快速排序的思想,快速排序的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的

  因此,我们可以借鉴快速排序的思想,通过设置两个指针来进行交换操作,从而减少移动次数,提高效率:

Step1.第一个指针初始化时指向数组的第一个数字,它只向后移动;

Step2.第二个指针初始化时指向数组的最后一个数字,它只向前移动。

Step3.在两个指针相遇之前,第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是偶数,并且第二个指针指向的数字是奇数,我们就交换这两个数字。

  下图展示了调整数组{1,2,3,4,5}使得奇数位于偶数前面的过程:

三、解决问题

3.1 代码实现

  (1)基本功能实现

    public static void ReorderOddEven(int[] datas)
    {
        if (datas == null || datas.Length <= 0)
        {
            return;
        }

        int begin = 0;
        int end = datas.Length - 1;
        int temp = -1;

        while (begin < end)
        {
            // 向后移动begin,直到它指向偶数
            while (begin < end && datas[begin] % 2 != 0)
            {
                begin++;
            }
            // 向前移动pEnd,直到它指向奇数
            while (begin < end && datas[end] % 2 == 0)
            {
                end--;
            }

            if (begin < end)
            {
                // 交换偶数和奇数
                temp = datas[begin];
                datas[begin] = datas[end];
                datas[end] = temp;
            }
        }
    }

  怎么样,看起来是不是和快速排序的代码如出一辙?

  (2)可扩展性实现

  如果把题目改成把数组中的数按照大小分为两部分,所有负数都在非负数的前面,又或者改改,变成把数组中的数分为两部分,能被3整除的数都在不能被3整除的数的前面。面对需求的变化,我们发现代码变化的部分很小,因此从可扩展性的角度考虑,我们可以改写上面的代码如下,这里利用了.NET中的“函数指针”—委托来实现。

  ①方法实现

    public static void ReorderOddEven(int[] datas, Predicate<int> func)
    {
        if (datas == null || datas.Length <= 0)
        {
            return;
        }

        int begin = 0;
        int end = datas.Length - 1;
        int temp = -1;

        while (begin < end)
        {
            // 向后移动begin,直到它指向偶数
            while (begin < end && !func(datas[begin]))
            {
                begin++;
            }
            // 向前移动pEnd,直到它指向奇数
            while (begin < end && func(datas[end]))
            {
                end--;
            }

            if (begin < end)
            {
                // 交换偶数和奇数
                temp = datas[begin];
                datas[begin] = datas[end];
                datas[end] = temp;
            }
        }
    }

  这里使用了.NET中的预定义委托Predicate,有不了解预定义委托的朋友可以阅读我另一篇博文:《.NET中那些所谓的新语法之三》,这里就不再赘述了。

  ②如何调用

    // 判断奇数还是偶数
    ReorderHelper.ReorderOddEven(numbers, new Predicate<int>((num) => num % 2 == 0));
    // 判断是能否被3整除
    ReorderHelper.ReorderOddEven(numbers, new Predicate<int>((num) => num % 3 == 0));

  这里使用了.NET中的Lambda表达式,同样,有不了解Lambda表达式的朋友也可以阅读我的另一篇博文:《.NET中那些所谓的新语法之三》,这里也就不再赘述了。

3.2 单元测试

  首先,这里封装了一个用于比较两个数组中的元素值是否相等的辅助方法:

    // 辅助方法:对比两个数组是否一致
    public bool ArrayEqual(int[] ordered, int[] expected)
    {
        if (ordered.Length != expected.Length)
        {
            return false;
        }

        bool result = true;
        for (int i = 0; i < ordered.Length; i++)
        {
            if (ordered[i] != expected[i])
            {
                result = false;
                break;
            }
        }

        return result;
    }

  (1)功能测试

    // Test1:输入数组中的奇数、偶数交替出现
    [TestMethod]
    public void ReorderTest1()
    {
        int[] numbers = { 1, 2, 3, 4, 5, 6, 7 };
        int[] expected = { 1, 7, 3, 5, 4, 6, 2 };
        ReorderHelper.ReorderOddEven(numbers);
        Assert.AreEqual(ArrayEqual(numbers, expected), true);
    }

    // Test2:输入数组中的所有偶数都出现在奇数的前面
    [TestMethod]
    public void ReorderTest2()
    {
        int[] numbers = { 2, 4, 6, 1, 3, 5, 7 };
        int[] expected = { 7, 5, 3, 1, 6, 4, 2 };
        ReorderHelper.ReorderOddEven(numbers);
        Assert.AreEqual(ArrayEqual(numbers, expected), true);
    }

    // Test3:输入数组中的所有奇数都出现在偶数的前面
    [TestMethod]
    public void ReorderTest3()
    {
        int[] numbers = { 1, 3, 5, 7, 2, 4, 6 };
        int[] expected = { 1, 3, 5, 7, 2, 4, 6 };
        ReorderHelper.ReorderOddEven(numbers);
        Assert.AreEqual(ArrayEqual(numbers, expected), true);
    }

  (2)特殊输入测试

    // Test4:输入的数组只包含一个数字-奇数
    [TestMethod]
    public void ReorderTest4()
    {
        int[] numbers = { 1 };
        int[] expected = { 1 };
        ReorderHelper.ReorderOddEven(numbers);
        Assert.AreEqual(ArrayEqual(numbers, expected), true);
    }

    // Test5:输入的数组只包含一个数字-偶数
    [TestMethod]
    public void ReorderTest5()
    {
        int[] numbers = { 2 };
        int[] expected = { 2 };
        ReorderHelper.ReorderOddEven(numbers);
        Assert.AreEqual(ArrayEqual(numbers, expected), true);
    }

    // Test6:NULL指针
    [TestMethod]
    public void ReorderTest6()
    {
        int[] numbers = null;
        int[] expected = null;
        ReorderHelper.ReorderOddEven(numbers);
        Assert.AreEqual(numbers, expected);
    }

  (3)测试结果

  ①用例通过情况

  ②代码覆盖率

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏五分钟学算法

五分钟看懂一个高难度的排序:堆排序

堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。

1092
来自专栏五分钟学算法

每天一算:Evaluate Reverse Polish Notation

我们会在每天早上8点30分准时推送一条LeetCode上的算法题目,并给出该题目的动画解析以及参考答案,每篇文章阅读时长为五分钟左右。

691
来自专栏书山有路勤为径

逆序数

LeetCode 315. Count of Smaller Numbers After Self

631
来自专栏机器学习和数学

[编程经验]Python中的Lambda,Map, Reduce小结

今天要和大家分享的是Python匿名函数(anonymous functions),也叫lambda函数。匿名函数的意思就是说这个函数没有显式的函数名,因为一般...

3305
来自专栏Python小屋

妙用Python内置函数int()快速计算等比数列前n项和

本文要点在于Python内置函数int()的用法,所以计算等比数列前n项和时没有使用数学上的公式Sn=a1*(1-q^n)/(1-q)。 一般遇到这样的问题,很...

5786
来自专栏nnngu

算法02 七大排序之:直接选择排序和堆排序

上一篇总结了交换排序的冒泡排序和快速排序。这一篇要总结的是选择排序,选择排序分为直接选择排序和堆排序,主要从以下几点进行总结。 1、直接选择排序及算法实现 2、...

3607
来自专栏chenjx85的技术专栏

leetcode-58-Length of Last Word

2096
来自专栏章鱼的慢慢技术路

浅谈main(),int main(),void main(),int main(void)四者之间的区别

1213
来自专栏小樱的经验随笔

C/C++中连接函数strcat的应用(简单讲解)

有位学弟问到我如何将两个字符连接起来,想想java/python里面可以直接用+连接起来,可是C/C++里面有没有这么方便的做法呢?

1092
来自专栏数据结构与算法

06:整数奇偶排序

06:整数奇偶排序 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 给定10个整数的序列,要求对其重新排序。排序要求: 1...

3756

扫码关注云+社区

领取腾讯云代金券