21. 调整数组顺序使奇数位于偶数前面

  • Post author:
  • Post category:其他




剑指offer 21 调整数组顺序使奇数位于偶数前面 LeetCode 905

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


示例:


输入:

nums = [1,2,3,4]


输出:

[1,3,2,4]


注:

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


提示:


  1. 0 <= nums.length <= 50000

  2. 1 <= nums[i] <= 10000



解法一: 利用双指针

建立一个和

nums

长度一样的数组

res

,遍历

nums

,当当前元素是奇数时从前往后放,

left++

, 当当前元素是偶数时,从后往前放,

right--

class Solution {
    public int[] exchange(int[] nums) {
        if(nums == null || nums.length == 0) return nums;
        int[] res = new int[nums.length];
        int left = 0;
        int right = nums.length-1;
        for(int i = 0;i < nums.length;i++){
            if(nums[i] % 2 != 0){//奇数从前往后放
                res[left++] = nums[i];
            }else{//偶数从后往前放
                res[right--] = nums[i];
            }
        }
        return res;

    }
}

在这里插入图片描述



解法二:快速排序思想

本质仍然是用到双指针的思想,但不需要额外的空间了,让

left

指向数组最左边,

right

指向数组最右边,

left

不断右移,直到指向的元素不是奇数时停下,

right

则向左边移动,直到指向的元素不是偶数时停下,然后交换两个指针指向的元素,在两个指针相遇之前,

left

指针总是位于

right

指针的前面,接着开始下一轮循环,退出循环的条件是

left>right

。实际上不难发现这其实就是快速排序思想中的一轮循环。

在这里插入图片描述

class Solution {
    public int[] exchange(int[] nums) {
        if(nums == null || nums.length == 0) return nums;
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            //这里left<nums.length的判断不能省,如全是奇数[1,3,5],不写该条件,left将出现数组下标越界,right同理
            while(left < nums.length && nums[left] % 2 != 0) left++;
            while(right >= 0 && nums[right] % 2 == 0) right--;
            /*这里的if判断也不能省,因为在交界处的时候,如[1,3,2,4]
            经过上面两个while后,left指着2,right指着3,是不需要交换了的*/
            if(left < right){
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
        return nums;
    }
}

在这里插入图片描述



扩展题:需要保证奇数和奇数,偶数和偶数之间的相对位置不变

需要保证奇数和奇数,偶数和偶数之间的相对位置不变,这和上面不太一样,上面的解法不能保证相对位置不变。例如对于

[1,2,3,4,5]

,调整后应该得到

[1,3,5,2,4]

,而不能是

[1,3,5,4,2]

这种相对位置改变的结果。

在这里插入图片描述



解题思路:

用到上面解法一的思路,但是需要先遍历数组计算出数组中奇数的个数

count

。而后不是将偶数从最后往前放了,而是从

count

的位置开始往后放,因为数组下标是从

0

开始的,

count

个奇数会占用前面

count-1

个下标的位置。



Java代码

class Solution {
    public int[] exchange(int[] nums) {
        if(nums == null || nums.length == 0) return nums;
        int count = 0for(int num : nums){//求出数组中奇数的个数
            if(num % 2 != 0){
                count++;
            }
        }
        
        int[] res = new int[nums.length];
        int left = 0;
        int right = count;
        for(int i = 0;i < nums.length;i++){
            if(nums[i] % 2 != 0){//奇数从前往后放
                res[left++] = nums[i];
            }else{//偶数从count处往后放
                res[right++] = nums[i];
            }
        }
        return res;

    }
}



版权声明:本文为YouMing_Li原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。