剑指Offer[21]-调整数组顺序使奇数位于偶数前面

题目

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

输入:nums = [1,2,3,4]
输出:[1,3,2,4] 
注:[3,1,2,4] 也是正确的答案之一。

python代码

class Solution(object):
    def exchange(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if len(nums)==0:
            return []
        out_1 = []
        out_2 = []
        for i in nums:
            if i%2==0:
                out_2.append(i)
            else:
                out_1.append(i)
        return out_1+out_2

上述的方法非常常规,直接遍历数组找奇数和偶数,并使用了额外的空间来储存奇数和偶数,时间复杂度和空间复杂度均为O(n)。

拓展

我们是否可以尝试不使用额外储存空间的前提下完成任务?当然可以,因为这个问题本质上就是元素的交换。

class Solution(object):
    def exchange(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if len(nums)==0:
            return []

        left_p = 0
        right_p = len(nums)-1

        while True:
            while nums[left_p]&1:
                left_p+=1
                if left_p>=right_p:
                    return nums
            while not nums[right_p]&1:
                right_p-=1
                if left_p>=right_p:
                    return nums
            nums[left_p],nums[right_p] = nums[right_p],nums[left_p]

上述代码直接在原数组上进行修改,没有使用额外的储存空间。
我们来简要分析一下思路,直接看while True:部分:

  • n&1用来判断是否为奇数,奇数:n&1=1,偶数n&1=0(只要一个整数的二进制最后一位是1,则一定为奇数,若为0,则是偶数);
  • while not is_k(nums[left_p]):从数组头部开始找偶数,当遇到偶数时停止;
  • while is_k(nums[right_p])::从数组尾部开始找奇数,找到奇数时停止;
  • 交换上述两个位置的元素,然后继续循环,直到它们在数组的某个位置‘碰头’就代表奇数和偶数交换结束。

做到这里,其实大家可能又会想到一种思路,快慢指针(假设两个指针从左侧出发,慢指针指向下一个奇数的位置,快指针往后搜索奇数,遇到奇数就与满指针的元素交换),其实它跟上述的方法均属于双指针法,只不过切入点不同(起始搜索的方向不同),本质思想是一致的。

发表评论

电子邮件地址不会被公开。