【牛客 - 剑指offer】JZ81 调整数组顺序使奇数位于偶数前面(二) 三种方案 Java实现

---

剑指offer题解汇总 Java实现

https://blog.csdn.net/guliguliguliguli/article/details/126089434

本题链接

知识分类篇 - 其他算法 - JZ81 调整数组顺序使奇数位于偶数前面(二)

题目

思路 & 代码

方案一 双指针（推荐）

1. 定义两个指针left和right
   • left指向数组中的第一个元素
   • right指向数组中的最后一个元素
2. left指针，在满足一定条件后，向右移动
   • 如果left指针当前所指的数组中的数是奇数，那么left++
   • 如果left指针当前所指的数组中的数是偶数，那么left指针保持不变
3. right指针，在满足一定条件后，向左移动
   • 如果right指针当前所指的数组中的数是偶数，那么right–
   • 如果right指针当前所指的数组中的数是奇数，那么right指针保存不变
4. 两个while循环结束以后，需要判断left和right指针是否已经超出了数组的索引范围，即left和right是否在[0，array.length-1]之间
   • 如果left、right均在该区间内，那么交换left和right所指向的数组中的值
   • 否则，退出最外层while循环，将当前的数组作为返回值返回

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param array int整型一维数组
     * @return int整型一维数组
     */
    public int[] reOrderArrayTwo(int[] array) {
        // write code here
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            //array[left]为奇数，left指针一直向右移
            while ((left < array.length) && ((array[left] & 1) != 0)) {
                left++;
            }
            //array[right]为偶数，right指针一直向左移
            while ((right >= 0) && ((array[right] & 1) == 0)) {
                right--;
            }
            if (left >= right || left >= array.length || right < 0) {
                break;
            }
            int temp = array[right];
            array[right] = array[left];
            array[left] = temp;
            left++;
            right--;
        }
        return array;
    }
}
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

方案二 统计奇数出现次数

1. 创建一个新的数组，该数组与形参传入的数组长度一致，之后作为返回值返回
2. 遍历数组中的值，统计奇数（或偶数）出现的次数odd
   • 下面的代码中，统计的是奇数出现的次数，因为要求奇数出现在整个数组的前半部分，所以统计奇数比较方便
3. 定义两个指针，一个指向0，一个指向odd，这样odd前面的odd个数正好能存储odd个数字，从下标是odd开始的都是偶数
4. 返回res

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param array int整型一维数组
     * @return int整型一维数组
     */
    public int[] reOrderArrayTwo(int[] array) {

        // write code here
        int[] res = new int[array.length];

        int odd = 0;
        for (int value : array) {
            if ((value & 1) != 0) {
                odd++;
            }
        }

        //x表示奇数下标
        //y表示偶数开始下标
        int x = 0, y = odd;
        for (int value : array) {
            if ((value & 1) != 0) {
                res[x++] = value;
            } else {
                res[y++] = value;
            }
        }

        return res;
    }
}
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

方案三 统计偶数出现的次数（思想与方案二类似）

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param array int整型一维数组
     * @return int整型一维数组
     */
    public int[] reOrderArrayTwo(int[] array) {

        // write code here
        int[] res = new int[array.length];

        int even = 0;
        for (int value : array) {
            if ((value & 1) == 0) {
                even++;
            }
        }

        //x表示奇数下标
        //y表示偶数开始下标
        int x = 0, y = array.length - even;
        for (int value : array) {
            if ((value & 1) != 0) {
                res[x++] = value;
            } else {
                res[y++] = value;
            }
        }

        return res;
    }
}
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