1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 21 题] “调整数组顺序使奇数位于偶数前面”做题记录

[剑指 Offer 第 2 版第 21 题] “调整数组顺序使奇数位于偶数前面”做题记录

第 21 题:调整数组使得奇数位于偶数之前

传送门:AcWing:调整数组顺序使奇数位于偶数前面牛客网 online judge 地址

输入一个整数数组,实现一个函数来调整该数组中数字的顺序。

使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分。

样例:

输入:[1,2,3,4,5]

输出: [1,3,5,2,4]

分析:这道题要注意的一点就是:保持原来的顺序,具体可以参考 LeetCode 第 88 题的策略,从后向前重新为数组赋值。

思路1:有点类似“两路快排”的思路。“两路快排”中有一些细节需要复习一下。双指针扫描:用两个指针分别从首尾开始,往中间扫描。扫描时保证第一个指针前面的数都是奇数,第二个指针后面的数都是偶数。每次迭代时需要进行的操作:

1、第一个指针一直往后走,直到遇到第一个偶数为止; 2、第二个指针一直往前走,直到遇到第一个奇数为止。 交换两个指针指向的位置上的数,再进入下一层迭代,直到两个指针相遇为止。 时间复杂度:当两个指针相遇时,走过的总路程长度是 n,所以时间复杂度是 O(n)

Python 代码:

  class Solution(object):
        def reOrderArray(self, array):
            """
            :type array: List[int]
            :rtype: void
            """
            # 特判
            size = len(array)
            if size < 2:
                return

            l = 0
            r = size - 1

            # 始终保持 [0,l) 是奇数
            # (r,size-1] 是偶数

            while True:
                while l <= r and array[l] & 1 == 1:
                    l += 1
                # 此时 l 来到了第一个偶数位置
                while r >= l and array[r] & 1 == 0:
                    r -= 1
                # 此时 r 来到了第一个奇数的位置

                # 这里一定是大于号,否则数组下标会越界
                # 一定要特别注意,写 == 号会出错,写 >= 是可以的,因为 == 成立的时候,不用交换
                if l > r:
                    break
                array[l], array[r] = array[r], array[l]
                l += 1
                r -= 1
            return array

C++ 代码:

liwei201910115_1.png

C++ 代码:

  class Solution {
    public:
        void reOrderArray(vector<int> &array) {
             int l = 0, r = array.size() - 1;
             while (l <= r) {
                 while (array[l] % 2 == 1) l ++ ;
                 while (array[r] % 2 == 0) r -- ;
                 if (l < r) swap(array[l], array[r]);
             }
        }
    };

思路2:把奇数数组复制出来,按照从后向前归并排序的做法完成。

Java 代码:

  import java.util.Arrays;

    public class Solution {
        // 保证奇数和奇数,偶数和偶数之间的相对位置不变。
        public void reOrderArray(int[] array) {
            int len = array.length;
            if (len == 0) {
                return;
            }
            // 奇数全部挪到缓存数组中
            int[] buff = new int[len];
            int j = -1;
            for (int i = 0; i < len; i++) {
                if (array[i] % 2 == 1) {
                    j++;
                    buff[j] = array[i];
                }
            }
            // 如果都没有奇数的话,程序终止
            if (j == -1) {
                return;
            }
            // 把偶数集中“挤”到数组的末尾
            // 然后再把缓存数组中的奇数倒序放入
            int k = len - 1;
            for (int i = len - 1; i >= 0; i--) {
                if (array[i] % 2 == 0) {
                    array[k] = array[i];
                    k--;
                }
            }
            while (j >= 0) {
                array[j] = buff[j];
                j--;
            }
        }

        public static void main(String[] args) {
            int[] arr = {1, 2, 3, 4, 5};
            Solution solution = new Solution();
            solution.reOrderArray(arr);
            System.out.println(Arrays.toString(arr));
        }
    }

Java 代码:

  import java.util.Arrays;

    public class Solution {
        // 保证奇数和奇数,偶数和偶数之间的相对位置不变。
        public void reOrderArray(int[] array) {
            int len = array.length;
            if (len == 0) {
                return;
            }
            // 奇数全部挪到缓存数组中
            int[] buff = new int[len];
            int j = -1;
            for (int i = 0; i < len; i++) {
                if (array[i] % 2 == 1) {
                    j++;
                    buff[j] = array[i];
                }
            }
            // 如果没有奇数,直接返回就可以了
            if (j == -1) {
                return;
            }
            // 从后向前赋值
            int k = len - 1;
            for (int i = len - 1; i >= 0; i--) {
                if (array[i] % 2 == 0) {
                    array[k] = array[i];
                    k--;
                }
            }
            while (j >= 0) {
                array[j] = buff[j];
                j--;
            }
        }
    }

扩展:书本上有这个问题更一般的做法。

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 21 题] “调整数组顺序使奇数位于偶数前面”做题记录

链接:https://www.javajike.com/article/3270.html

« [剑指 Offer 第 2 版第 20 题] “表示数值的字符串”做题记录
[剑指 Offer 第 2 版第 22 题] “链表中倒数第k个结点”做题记录.md»

相关推荐

QR code