leetcode - [922] Sort Array By Parity II

2020/07/15

问题描述

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.

Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.

You may return any answer array that satisfies this condition.

给你一个非负整数数组,一半是奇数,一般是偶数。

排序一下数组,满足索引为偶数时,其值也是偶数,奇数同理。

只要满足以上条件,内部顺序任意。

举个例子:

Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Update at 2020_0718

之间的解法判断条件太过于复杂,对于这道题来说没有必要,来看一种更简洁的解法。

思路是这样的,

首先,我们需要两个指针,o1开始代表奇数,e0开始代表偶数。

注意,每次只判断A[e]是否为偶数,如果是,e = e + 2

否则,将两个指针对应的值互换,并且o = o + 2,注意e指针不动。

来看下示意图:

实现如下:

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

解法1

我的想法是这样的:

首先,需要左右两个指针,注意这里需要一次走两步。

而且,循环结束的条件为i < n && j >= 0

然后,因为左指针代表的是偶数,所以一旦遇到奇数就停下。

右指针同理,不过它代表的是奇数,

等到左右指针都停下时,互换即可。

来看下实现:

class Solution {
    public int[] sortArrayByParityII(int[] A) {
        
        int n = A.length;
        int i = 0, j = n - 1;
        
        while (i < n && j >= 0){
            // even
            while (i < n  && (A[i] & 1) == 0){
                i += 2;
            }
            while (j >= 0 && (A[j] & 1) == 1){
                j -= 2;
            }
            if (i < n && j >= 0){
                swap(A, i, j);
                i += 2;
                j -= 2;
            }
        }
        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