【剑指Offer】21. 调整数组顺序使奇数位于偶数前面

亦凉 2022-11-25 13:07 12阅读 0赞

[NowCoder][]

## 题目描述 ##

需要保证奇数和奇数，偶数和偶数之间的相对位置不变，这和书本不太一样。

## 解题思路 ##

### 新建数组 ###

方法一：创建一个新数组，时间复杂度 O(N)，空间复杂度 O(N)。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70]

public class Solution { 
        public void reOrderArray(int [] array) { 
            int countji = 0;
            for(int i : array) { 
                if(!iso(i))
                    countji++;
            }
            int[] copy = array.clone();
            int i = 0, j = countji;
            for(int n : copy) { 
                if(n % 2 == 1)
                    array[i++] = n;
                else
                    array[j++] = n;
            }
        }
        private boolean iso(int n) { 
            return n % 2 == 0;
        }
    }

### 冒泡 时间换空间 ###

方法二：使用冒泡思想，每次都当前偶数上浮到当前最右边。时间复杂度 O(N2)，空间复杂度 O(1)，时间换空间。

public class Solution { 
        public void reOrderArray(int [] array) { 
            int len = array.length;
            for(int i = len-1; i > 0; i--) { 
                for(int j = 0; j < i; j++) { 
                    if(iso(array[j]) && !iso(array[j+1])) 
                        swap(array, j, j+1);
                }
            }
        }
        // 判断偶数
        private boolean iso(int n) { 
            return n%2 == 0;
        }
        // 交换
        private void swap(int[] arr, int i, int j) { 
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

[NowCoder]: https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593?tpId=13&tqId=11166&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=bennyrhys@163.com
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70]: /images/20221124/dd32d1d725fb449aba2242e43a821753.png