leetcode - [905] Sort Array By Parity

2020/07/15

问题描述

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

给你一个非负数整数,将偶数放在前半部分,奇数放在后面部分。

内部的顺序都行。

举个例子:

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Update at 2020_0718

这道题其实没有必要多用一个border指针:

如果左边元素是偶数,直接跳过当前元素。

否则与右边元素交换,然后右指针-1,左指针不变即可。

class Solution {
    
    private void swap(int[] a, int l, int r){
        int t = a[l];
        a[l]  = a[r];
        a[r]  = t;
    }
    
    public int[] sortArrayByParity(int[] A) {
        
        int n = A.length;
        int l = 0, r = n - 1;
        while (l < r){
            if ((A[l] & 1) == 0){
                l++;
            } else {
                swap(A, l, r--);
            }
        }
        return A;
    }
}

解法1

说下思路,使用左右两个指针,外加一个代表左边偶数边界的指针border

如果左边的元素是奇数,则左右元素互换,且右指针-1

否则,肯定就是偶数,则左指针和边界指针border对应的元素互换,且均+1

来看下实现:

class Solution {
    public int[] sortArrayByParity(int[] A) {
        
        int n = A.length;
        int l = 0, r = n - 1, b = 0;
        while (l <= r){
            if ((A[l] & 1) == 0){
                swap(A, l++, b++);
            } else {
                swap(A, l, r--);
            }
        }
        return A;
    }
    
    private void swap(int[] a, int l, int r){
        int t = a[l];
        a[l] = a[r];
        a[r] = t;
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory