每天一道leetcode905-按奇偶排序数组

乔戈里

发布于 2019-09-17 14:51:33

3110

发布于 2019-09-17 14:51:33

文章被收录于专栏：Java那些事

前言

昨天贴的代码和题有错误，今天重发一下，抱歉哈~

2018.11.12号打卡明天的题目： https://leetcode.com/problems/merge-intervals/

题目

每天一道leetcode905-按奇偶排序数组分类：数组中文链接： https://leetcode.com/problems/sort-array-by-parity/description/ 英文链接 https://leetcode.com/problems/sort-array-by-parity/description/

题目详述

给定一个非负整数数组 A，返回一个由 A 的所有偶数元素组成的数组，后面跟 A 的所有奇数元素。你可以返回满足此条件的任何数组作为答案。示例：输入：[3,1,2,4] 输出：[2,4,3,1] 输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。提示： 1 <= A.length <= 5000 0 <= A[i] <= 5000

题目详解

使用额外空间的思路

就是使用一个新的数组B，去存，每次判断原来的数组是不是偶数，是偶数就存到前面，是奇数就存到后面

代码

class Solution {
    public int[] sortArrayByParity(int[] A) {
        if(A.length == 0)
            return A;
        int [] B = new int [A.length];
        int begin = 0;
        int end = B.length - 1;
        for(int i=0;i<A.length;i++)
        {
            if(A[i] % 2 == 0)
            {
                B[begin] = A[i];
                begin++;
            }
            else{
                B[end] = A[i];
                end--;
            } 
        }
        return B;
    }
}

代码讲解

10-14行，是判断偶数，如果是偶数，那么就存到B的前面，同时注意begin++
15-18行，是判断是奇数了，如果是奇数，那么就存到后面，同时end--;

不使用额外空间的思路

直接在原数组进行操作，一个i从0数组开头开始，j从数组末尾开始；
依次去判断，如果A[i]是偶数，直接i++,如果A[j]是奇数直接j--;（为啥呢，因为前面的数已经是偶数了，满足条件，就往后判断呗~后面的是奇数也是同理）
如果A[i]是奇数的同时A[j]是偶数，那么就交换这两个数
由于这个是两端到中间遍历，速度肯定比上一个从头到尾快

代码

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int i=0, j= A.length - 1;
        while(i < j)
        {
            if(A[i] % 2 == 1 && A[j] %2 == 0)
            {
                int temp = A[i];
                A[i] = A[j];
                A[j] = temp;
                i++;
                j--;
            }
            else if(A[i] % 2 == 0)
            {
                i++;
            }
            else if(A[j] % 2 == 1)
            {
                j--;
            }
        }
        return A;
    }
}