【搞定算法】数组的奇偶位置问题

深碍√TFBOYSˉ_ 2021-11-23 09:08 242阅读 0赞

> 博主秋招提前批已拿百度、字节跳动、拼多多、顺丰等公司的offer，可加微信：**pcwl\_Java** 一起交流秋招面试经验，可获得博主的秋招简历和复习笔记。

> `题目：给定一个整型数组，请在原地调整这个数组，保证要么偶数位置上都是偶数，或者奇数位置上都是奇数。 要求：时间复杂度 O(N)，额外空间复杂度 O(1)。`

*   这个题目需要注意的是：偶数在偶数的位置、奇数在奇数的位置，这两个条件满足其一就行了。

下面的代码中，将最后一个元素作为发货点，根据自己值的奇偶性和当前数组 odd 和 even 指针指向的元素进行交换，这样不停的交换。最后如果有一个指针越界了，那对应的规则就排在了对应的位置上了。

这个题目的代码量不是很大，也没有特殊的算法，但是编程技巧确实很好。

public class EvenInEvenOddInOdd {
    
        public static void getOrder(int[] arr){
            if(arr == null || arr.length < 2){
                return;
            }
            int even = 0;  // 指向偶数的位置
            int odd = 1;   // 指向奇数的位置
            // 发货点：每次把最后一个数根据它是奇数还是偶数和前面对应奇偶指针上的数互换位置
            int end = arr.length - 1;
            while(odd < arr.length && even < arr.length){
                if(arr[end] % 2 == 0){
                    // 往even指针上发货,然后even指针后移两位
                    swap(arr, end, even);
                    even += 2;
                }else{
                    // 往odd指针上发货,然后odd指针后移两位
                    swap(arr, end, odd);
                    odd += 2;
                }
            }
        }
    
        public static void swap(int[] arr, int i, int j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }