Ming
0%

LeetCode-922

Posted on Edited on In

题目

Snipaste_2020-11-12_08-55-45.png

结果

Snipaste_2020-11-12_08-59-45.png

代码

原地排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int[] sortArrayByParityII(int[] A) {
        for (int i = 0; i < A.length; i++) {
            if (i % 2 != A[i] % 2) {
                if (i % 2 == 0) {
                    swap(A, i, nextGuy(A, i, false));
                } else {
                    swap(A, i, nextGuy(A, i, true));
                }
            }
        }
        return A;
    }

    // when flag is true: find next even index
    // when flag is false: find next odd index
    private int nextGuy(int[] nums, int index, boolean flag) {
        if (flag) {
            for (int i = index + 1; i < nums.length; i++) {
                if (i % 2 == 0 && nums[i] % 2 != 0) {
                    return i;
                }
            }
        } else {
            for (int i = index + 1; i < nums.length; i++) {
                if (i % 2 != 0 && nums[i] % 2 == 0) {
                    return i;
                }
            }
        }
        throw new RuntimeException("IMPOSSIBLE");
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

新的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] sortArrayByParityII(int[] A) {
        if (A.length == 1) {
            return A;
        }
        int[] ans = new int[A.length];
        int index1 = 0;
        int index2 = 1;
        for (int i = 0; i < A.length; i++) {
            if (A[i] % 2 == 0) {
                ans[index1] = A[i];
                index1 += 2;
            } else {
                ans[index2] = A[i];
                index2 += 2;
            }
        }
        return ans;
    }
}

复杂度

时间复杂度：O（n²），O（n）

空间复杂度：O（1）