剑指offer 面试题21. 调整数组顺序使奇数位于偶数前面（易）

这个题目的关键，是写出可扩展的代码，本题的要求是使奇数位于偶数前面，那么使负数位于非负数前面，使3的倍数位于3的非倍数前面的功能也要能够直接拓展实现才行。

Question

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

示例：

1
2
输入：nums = [1,2,3,4]
输出：[1,3,2,4]

注：[3,1,2,4] 也是正确的答案之一。

提示： 1 <= nums.length <= 50000； 1 <= nums[i] <= 10000.

测试样例

功能测试（输入数组中的奇数、偶数交替出现；输入的数组中所有偶数都出现在奇数的前面；输入的数组中所有奇数都出现在偶数的前面）。 特殊输入测试（输入 nullptr 指针；输入的数组只包含一个数字）。

考点

考查应聘者的快速思维能力。要在短时间内按照要求把数组分隔成两部分不是一件容易的事情，需要较快的思维能力。 对于已经工作了几年的应聘者，面试官还将考查其对扩展性的理解，要求应聘者写出的代码具有可重用性。

Intuition

暴力破解

从头扫描这个数组，每碰到一个偶数，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位，这时把该偶数放入这个空位。由于每碰到一个偶数就需要移动 \(O(n)\) 个数字，因此总的时间复杂度是 \(O(n^2)\)。但是，这种方法不能让面试官满意。不过如果我们在听到题目之后能马上说出这种解法，那么面试官至少会觉得我们的思维非常敏捷。通过修改 func 函数可以是随意调整前移条件，实现代码的可扩展性。

双指针

实际上就是快排。

因此，我们可以维护两个指针：第一个指针初始化时指向数组的第一个数字，它只向后移动；第二个指针初始化时指向数组的最后一个数字，它只向前移动。在两个指针相遇之前，第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是偶数，并且第二个指针指向的数字是奇数，则交换这两个数字。 下面以一个具体的例子，如输入数组{1，2，3，4，5}来分析这种思路。在初始化时，把第一个指针指向数组第一个数字1，而把第二个指针指向最后一个数字5，如图3.6（a）所示。第一个指针指向的数字1是一个奇数，不需要处理，我们把第一个指针向后移动，直到碰到一个偶数2。此时第二个指针已经指向了奇数，因此不需要移动。此时两个指针指向的位置如图3.6（b）所示。这时候我们发现偶数2位于奇数5的前面，符合交换条件，于是交换这两个指针指向的数字，如图3.6（c）所示。 接下来我们继续向后移动第一个指针，直到碰到下一个偶数4，并向前移动第二个指针，直到碰到第一个奇数3，如图3.6（d）所示。我们发现第二个指针已经在第一个指针的前面了，表示所有的奇数都已经在偶数的前面了。此时的数组是{1，5，3，4，2}，的确是奇数位于数组的前半部分而偶数位于数组的后半部分。通过修改 func 函数可以是随意调整前移条件，实现代码的可扩展性。

Snipaste_2020-05-06_23-52-05.png

Code

  • 暴力破解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import unittest
from typing import List


class Solution:
    def func(self, number):
        return number & 1 == 0  # 偶数的二进制表示，第一位必然为0。

    def exchange(self, nums: List[int]) -> List[int]:
        _len = len(nums)
        if not _len:  return []
        i = 0
        count = 0
        while i < _len:
            if i + count == _len:  # 完成全部移动
                break
            if self.func(nums[i]):  # 偶数
                tmp = nums[i]
                for j in range(i, _len-1):
                    nums[j] = nums[j+1]
                nums[_len-1] = tmp
                count += 1
                # i -= 1
            else:
                i += 1
        return nums


class TestSolution(unittest.TestCase):
    def setUp(self):
        self.test_class = Solution()

    def test_solution(self):
        inputs = [
            # 功能测试
            [2,16,3,5,13,1,16,1,12,18,11,8,11,11,5,1],
            # 边界值的测试
            # 特殊样例
        ]
        answers = [
            [3,5,13,1,1,11,11,11,5,1,2,16,16,12,18,8],
        ]
        res = []
        for i in range(len(inputs)):
            res.append(self.test_class.exchange(inputs[i]))
        self.assertEqual(res, answers)
 
    def tearDown(self):
        del self.test_class


if __name__ == "__main__":
    unittest.main()
  • 双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def func(self, number):
        return number & 1 == 0  # 偶数的二进制表示，第一位必然为0。

    def exchange(self, nums: List[int]) -> List[int]:
        _len = len(nums)
        if not _len:  return []
        p1 = 0
        p2 = _len -1
        while p1 < p2:
            # 向后移动p1 直到遇到偶数
            while p1 < p2 and not self.func(nums[p1]):  # 遇到奇数就继续后移
                p1 += 1

            # 向前移动p2 直到遇到奇数
            while p1 < p2 and self.func(nums[p2]):  # 遇到偶数就继续前移
                p2 -= 1
            
            # 交换
            if p1 < p2:
                tmp = nums[p1]
                nums[p1] = nums[p2]
                nums[p2] = tmp

        return nums